Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
Here's a working C++ code.
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
set<string> dictionary;
void populate_dictionary();
bool search_dictionary(string s);
void possible_concatenations(string s);
int main()
{
string s="bedbathandbeyond";
populate_dictionary();
possible_concatenations(s);
return 0;
}
void populate_dictionary()
{
dictionary.insert("bed");
dictionary.insert("bat");
dictionary.insert("bath");
dictionary.insert("and");
dictionary.insert("hand");
dictionary.insert("beyond");
}
bool search_dictionary(string s)
{
set<string>::iterator itr;
for(itr=dictionary.begin(); itr!=dictionary.end(); itr++)
{
if(*itr==s)
return true;
}
return false;
}
void possible_concatenations(string s)
{
static vector<string> v;
if(s=="")
{
for(int i=0; i<v.size(); i++)
cout<<v[i]<<" ";
cout<<endl;
return;
}
string sub;
for(int i=1; i<=s.size(); i++)
{
sub=s.substr(0, i);
//cout<<sub<<endl;
if(search_dictionary(sub))
{
v.push_back(sub);
possible_concatenations(s.substr(i));
v.pop_back();
}
}
}
vector<vector<string>> PWC (string A, unordered_set <string> & dict)
{
vector <vector<string>> result;
if(A.size() == 0) return result;
string temp;
for(int i = 1; i < A.size(); i ++)
{
temp = A.substr(0, i);
if(dict.fine(temp) != dict.end())
{
vector<string> set;
set.push_back(temp);
PWC( A.substr(i), dict, result, set);
}
}
return result;
}
void PWC (string A, unordered_set <string> & dict, vector <vector<string>> & result, vector<string> subset)
{
if(A.size() == 0) {
result.push_back(subset);
return;
}
string temp;
for(int i = 1; i < A.size(); i ++)
{
temp = A.substr(0, i);
if(dict.fine(temp) != dict.end())
{
subset.push_back(temp);
subset.push_back(temp);
PWC( A.substr(i), dict, result, subset);
}
}
public static Set< String > findWords(String s, List< String > dictionary, int length) {
if (length <= 0) {
return new HashSet< String >();
}
Set< String > toReturn = new HashSet<>();
for (int i = 0; i + length <= s.length(); i++) {
String p = s.substring(i, i + length);
if (dictionary.contains(p)) {
toReturn.add(p);
}
}
toReturn.addAll(findWords(s, dictionary, length - 1));
return toReturn;
}
pseudo code:
- Marcello Ghali February 20, 2015