Facebook Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
Great solution, but i believe minor optimization may be made - you want to check only subwords that starts at start of string or after soe concatenation and you don't need to continue after you found first concatenation to this symbol
So
if (table[j] || j == 0) {
String subWord=word.substring(j,i+1);
if(hs.contains(subWord))
table[i+1]=true;
break;
}
instead of
String subWord=word.substring(j,i+1);
if(hs.contains(subWord))
{
if(table[j]) table[i+1]=true;
}
class StringDictionary{
public:
bool checkConcatenation(unordered_set<string>& dictionary, string str){
if(str.length() == 0) return true;
for(int i = 1; i <= str.length(); i ++){
string t = str.substr(0,i);
if(dictionary.find(t)!= dictionary.end()){
if(checkConcatenation(dictionary, str.substr(i))){
return true;
}
}
}
return false;
}
};
public static boolean isKeyFromDic(String key, String[] words, int index) {
if (key.length() > 0 && index == key.length()) return true;
for (String word : words) {
if (index + word.length() <= key.length()) {
String subWord = key.substring(index, index + word.length());
if (subWord.equals(word)) {
return isKeyFromDic(key, words, index + word.length());
}
}
}
return false;
}
private static boolean isConcatenated(HashSet<String> dict, String input, int offset) {
if (input.length() == offset) {
return true; // nothing to process
}
for (int i=offset; i<input.length(); i++) {
String sub = input.substring(offset, i+1);
if (dict.contains(sub)) {
boolean isConcatenated = isConcatenated(dict, input, i+1);
if (isConcatenated) return true;
}
}
return false;
}
def f(key,words):
if len(key) == 0:
return True
for word in words:
if key.beginswith(word) and f(key[len(word):], words):
return True
return False
Nice solution (came up with a very similar one myself).
But it won't work for a corner case:
f('', words) != False
Also the substring comparison function is startswith() (not beginswith())
def check_dict(dictionary, word):
for w in dictionary:
if word.startswith(w):
if len(w) == len(word):
return True
else:
return check_dict(dictionary, word[len(w):])
return False
public class Dictionary {
private HashSet<String> dictionary;
public static void main(String[] args)
{
Dictionary mDictionary = new Dictionary();
String key = "hellohello2";
System.out.println("===========================");
mDictionary.findConcatenations(key);
System.out.println("===========================");
mDictionary.findConcatenations("hellhellhellhellhell");//yes
System.out.println("===========================");
mDictionary.findConcatenations("superman");//no
System.out.println("===========================");
mDictionary.findConcatenations("hellhelloohellohell");//yes
System.out.println("===========================");
mDictionary.findConcatenations("hellhelloowhellohell");//no
}
public Dictionary() {
this.dictionary = new HashSet<String>(Arrays.asList("hello", "helloo", "hell", "super", "world"));
}
public void findConcatenations(String key){
System.out.println("For Key: " + key);
boolean[] checkArray = new boolean[key.length()+1];
int startPoint = 0;
int iterator = 1;
boolean wordMatched = false;
while(iterator<=key.length())
{
String subWord = key.substring(startPoint, iterator);
if(dictionary.contains(subWord))
{
checkArray[iterator] = true;
wordMatched = true;
}else if(wordMatched)
{
startPoint = --iterator;
wordMatched = false;
}
iterator++;
}
if(checkArray[key.length()]==true)
System.out.println("Answer: Perfect!");
else
System.out.println("Answer: :(");
}
}
The above code has been written with the help of the first answer. It runs at O(n), which is better than the first answer's O(n^2). [if I'm not wrong, lol]
This can be done in linear time using memoization. Here is a code in python:
class Solver:
def __init__(self , d):
self.dict = d
def __check__(self , index):
if index >= self.size:
return index==self.size
if self.lookup[index]!=-1:
return self.lookup[index]==1
for word in self.dict:
if self.txt[index:].startswith(word) and self.__check__(index+len(word)):
self.lookup[index] = 1
return True
self.lookup[index]==0
return False
def is_concatenation(self,s):
self.size = len(s)
self.txt = s
self.lookup = [-1 for _ in xrange(self.size)]
return self.__check__(0)
Everytime __check__ is called on an index, it gets computes the valueonly if it was not computed earlier. This means that any computation happens at max once for very index, giving a linear time complexity.
Fully build able solution
#include <iostream>
#include <unordered_set>
using namespace std;
bool is_concat( string str, unordered_set<string> dict );
int main( int argc, char ** argv ){
string in("Ilovepancakesbaconeggswaffles");
unordered_set<string> dict({ "waffles", "pancakes", "bacon", "eggs", "love", "I" });
cout << is_concat( in, dict ) << endl;
return 0;
}
bool is_concat( string str, unordered_set<string> dict ){
bool found_match = false;
for( int i = 0; i < str.length(); ++i ){
for( const auto & word : dict ){
if( word[0] == str[i] ){
if(word == str.substr(i, word.length())){
cout << "word: " << word << "is in the string" << endl;
i += word.length() - 1;
found_match = true;
}
}
}
if(!found_match){
return false;
}
}
return true;
}
CSCOMS.java
-----------------------------
public class CSCOMS {
private Set<String> stringSet;
public CSCOMS(String dictionary[]){
stringSet = new HashSet<String>();
for(int i = 0; i < dictionary.length; i++){
stringSet.add(dictionary[i]);
}
}
public boolean checkIfComposedOfMultipleString(String entry){
if(entry.length() == 0){
return true;
}
boolean result = false;
for(int i = 0; i < entry.length(); i++){
String token = entry.substring(0, i + 1);
if(stringSet.contains(token)){
result = checkIfComposedOfMultipleString(entry.substring(i + 1));
}
if(result){
break;
}
}
return result;
}
}
App.java
-----------------------------
public class App
{
public static void main( String[] args ){
String dictionary[] = {"world", "hello", "super", "hell"};
CSCOMS cscoms = new CSCOMS(dictionary);
String values[] = {"helloworld", "superman", "hellohello", "superhell", "hellsuper"};
System.out.print("Dictionary contents: ");
for(int i = 0; i < dictionary.length; i++){
System.out.print(dictionary[i] + " ");
}
System.out.println();
for(int i = 0; i < values.length; i++) {
System.out.println("\"" + values[i] + "\" --> " + cscoms.checkIfComposedOfMultipleString(values[i]));
}
}
}
CSCOMS.java
-----------------------------
public class CSCOMS {
private Set<String> stringSet;
public CSCOMS(String dictionary[]){
stringSet = new HashSet<String>();
for(int i = 0; i < dictionary.length; i++){
stringSet.add(dictionary[i]);
}
}
public boolean checkIfComposedOfMultipleString(String entry){
if(entry.length() == 0){
return true;
}
boolean result = false;
for(int i = 0; i < entry.length(); i++){
String token = entry.substring(0, i + 1);
if(stringSet.contains(token)){
result = checkIfComposedOfMultipleString(entry.substring(i + 1));
}
if(result){
break;
}
}
return result;
}
}
App.java
-----------------------------
public class App
{
public static void main( String[] args ){
String dictionary[] = {"world", "hello", "super", "hell"};
CSCOMS cscoms = new CSCOMS(dictionary);
String values[] = {"helloworld", "superman", "hellohello", "superhell", "hellsuper"};
System.out.print("Dictionary contents: ");
for(int i = 0; i < dictionary.length; i++){
System.out.print(dictionary[i] + " ");
}
System.out.println();
for(int i = 0; i < values.length; i++) {
System.out.println("\"" + values[i] + "\" --> " + cscoms.checkIfComposedOfMultipleString(values[i]));
}
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
class Main{
public static void main(String[] args){
Set<String> dictionary = new HashSet<String>();
dictionary.add("back");
dictionary.add("new");
dictionary.add("golf");
dictionary.add("run");
dictionary.add("o");
dictionary.add("omaha");
dictionary.add("nebraska");
dictionary.add("page");
List<String> testStrings = new ArrayList<String>();
//True cases.
testStrings.add("newback");
testStrings.add("nebraska");
testStrings.add("o");
testStrings.add("backnewgolfrunoomahanebraskapage");
testStrings.add("oomahapageo");
//False cases
testStrings.add("car");
testStrings.add("zap");
testStrings.add("oomahe");
testStrings.add("pages");
testStrings.add("backnewgolfrunoomahanebraskapages");
for(String testString : testStrings){
System.out.println(testString + " - " + isComposed(testString, dictionary));
}
}
private static boolean isComposed(String key, Set<String> dictionary){
int length = key.length();
LinkedList<SearchNode> searchNodes = new LinkedList<SearchNode>();
searchNodes.add(new SearchNode(0));
Map<String, LinkedList<String>> shortcutMap = new HashMap<String, LinkedList<String>>();
for(String word : dictionary){
String newKey = word.substring(0, 1);
if(!shortcutMap.containsKey(newKey)){
shortcutMap.put(newKey, new LinkedList<String>());
}
shortcutMap.get(newKey).add(word);
}
//printShortcutmap(shortcutMap);
while(!searchNodes.isEmpty()){
int ptrOrig = searchNodes.getFirst().getPtr();
int ptr = ptrOrig;
searchNodes.removeFirst();
String ltr = key.substring(ptr, ptr + 1);
if(!shortcutMap.containsKey(ltr)){
continue;
}
LinkedList<String> subDic = shortcutMap.get(ltr);
for(String wrd : subDic){
ptr = ptrOrig;
int wrdLen = wrd.length();
if(wrdLen == 1){
if(ptr + 1 == length){
return true;
}
searchNodes.add(new SearchNode(ptr + 1));
continue;
}
ptr++;
boolean match = false;
if(length - ptr >= wrdLen - 2){
match = true;
for(int i = 1; i < wrdLen && ptr < length ; i++){
if(!key.substring(ptr, ptr + 1).equals(wrd.substring(i, i + 1))){
match = false;
break;
}
ptr++;
}
}
if(match){
if(ptr == length){
return true;
}
searchNodes.add(new SearchNode(ptr));
}
}
}
return false;
}
private static void printShortcutmap(Map<String, LinkedList<String>> map){
for(Map.Entry<String, LinkedList<String>> entry : map.entrySet()){
System.out.println(entry.getKey());
for(String word : entry.getValue()){
System.out.println(" " + word);
}
System.out.println();
}
}
private static class SearchNode{
int ptr;
public SearchNode(int ptr){
this.ptr = ptr;
}
public int getPtr(){
return ptr;
}
}
}
public boolean checkConcatenations(String S){
boolean isStringConcatenationsOfStrings = false;
HashSet<String> dictionary = new HashSet<String>();
dictionary.add("world");
dictionary.add("hello");
dictionary.add("super");
dictionary.add("hell");
ArrayList<String> foundMatch = new ArrayList<String>();
int stringLength = S.length();
String subString = "";
for ( int index = 0 ; index < stringLength; index++){
subString += S.charAt(index);
int lenOfArray = foundMatch.size();
if ( lenOfArray > 0){
if(dictionary.contains(subString)){
foundMatch.add(subString);
subString = "";
}
String temp = subString;
for (int j = lenOfArray-1; j >= 0 && subString != "" ; j--){
temp = foundMatch.get(j) + temp;
if (dictionary.contains(temp)){
foundMatch.add(subString);
subString = "";
}
}
}
else if (dictionary.contains(subString)){
foundMatch.add(subString);
subString = "";
}
}
String result = "";
for (int index = 0; index < foundMatch.size(); index++){
result += foundMatch.get(index);
}
if (result.equals(S)){
isStringConcatenationsOfStrings = true;
}
return isStringConcatenationsOfStrings;
}
dictionary = {'world':'', 'hello':'', 'super':'', "hell":''}
def isValidConcatination(string):
if len(string) == 0:
return True
for i in range(len(string)+1):
if string[:i] in dictionary:
if isValidConcatination(string[i:]):
return True
return False
O(n^2)
A DP solution.
Let T(i) denotes if s.substr(i) can be split into words of the dict, then
T(i) = false || T(i + W1) || T(i + W2) || ... , if s.substr(i, Wi) is a valid word.
bool wordBreak(string s, unordered_set<string> &dict) {
if(s.empty())
return true;
if(dict.empty())
return false;
size_t maxlen = 0, minlen = -1;
for(const auto & w : dict){
maxlen = max(maxlen, w.size());
minlen = min(minlen, w.size());
}
vector<bool> dp(s.size() + 1);
dp[0] = true;
for(size_t i = 0;i < s.size();++i){
for(size_t j = minlen;j <= i + 1 && j <= maxlen;++j){
if(!dp[i + 1 - j])
continue;
if(dict.count(s.substr(i + 1 - j, j)) > 0){
dp[i + 1] = true;
break;
}
}
}
return dp.back();
}
@Test
public void testWordsFromDict() {
String[] dict = {"hell", "world", "hello", "super" };
Integer total = 0;
assertFalse(removePrefix("hellworl", dict));
assertTrue(removePrefix("hellworld", dict));
assertTrue(removePrefix("helloworld", dict));
assertFalse(removePrefix("helloworl", dict));
assertTrue(removePrefix("hellohello", dict));
assertTrue(removePrefix("hellohelloworld", dict));
assertFalse(removePrefix("superman", dict));
assertFalse(removePrefix("asuperman", dict));
assertTrue(removePrefix("super", dict));
}
public boolean removePrefix(String key,String[] dict) {
if (key.length() == 0) {
return true;
}
List<String> existingWords = new ArrayList<String>();
for (String word : dict) {
System.out.println("1");
if (key.startsWith(word)) {
existingWords.add(word);
}
}
int total = 0;
for (String word : existingWords) {
System.out.println("2");
if (removePrefix(key.substring(word.length()), dict)) {
total += 1;
}
}
return total > 0;
}
public class WordsFromDictTest {
@Test
public void testWordsFromDict() {
String[] dict = {"hell", "world", "hello", "super"};
assertFalse(removePrefix("hellworl", dict));
assertTrue(removePrefix("hellworld", dict));
assertTrue(removePrefix("helloworld", dict));
assertFalse(removePrefix("helloworl", dict));
assertTrue(removePrefix("hellohello", dict));
assertTrue(removePrefix("hellohelloworld", dict));
assertFalse(removePrefix("man", dict));
assertFalse(removePrefix("superman", dict));
assertFalse(removePrefix("asuperman", dict));
assertTrue(removePrefix("super", dict));
}
public boolean removePrefix(String key,String[] dict) {
List<String> existingWords = new ArrayList<String>();
for (String word : dict) {
if (key.startsWith(word)) {
existingWords.add(word);
}
}
int total = 0;
for (String word : existingWords) {
if (key.substring(word.length()).length() > 0) {
if (removePrefix(key.substring(word.length()), dict)) {
total += 1;
}
}
else {
total += 1;
}
}
return total > 0;
}
}
public class WordsFromDictTest {
@Test
public void testWordsFromDict() {
String[] dict = {"hell", "world", "hello", "super"};
assertFalse(removePrefix("hellworl", dict));
assertTrue(removePrefix("hellworld", dict));
assertTrue(removePrefix("helloworld", dict));
assertFalse(removePrefix("helloworl", dict));
assertTrue(removePrefix("hellohello", dict));
assertTrue(removePrefix("hellohelloworld", dict));
assertFalse(removePrefix("man", dict));
assertFalse(removePrefix("superman", dict));
assertFalse(removePrefix("asuperman", dict));
assertTrue(removePrefix("super", dict));
}
public boolean removePrefix(String key,String[] dict) {
List<String> existingWords = new ArrayList<String>();
for (String word : dict) {
if (key.startsWith(word)) {
existingWords.add(word);
}
}
int total = 0;
for (String word : existingWords) {
if (key.substring(word.length()).length() > 0) {
if (removePrefix(key.substring(word.length()), dict)) {
total += 1;
}
}
else {
total += 1;
}
}
return total > 0;
}
}
class Check {
public boolean checkIt(String[] dict, String str) {
int length = str.length();
int newLenth = 0;
for (int i = 0; i <= dict.length - 1; i++) {
while (true) {
if (str.contains(dict[i])) {
newLenth = newLenth + dict[i].length();
int value = str.indexOf(dict[i]);
if (value == 0) {
if (str.length() == dict[i].length()) {
str = "";
} else {
str = str.substring(dict[i].length(), str.length());
}
} else {
if (value + dict[i].length() >= length) {
str = str.substring(0, value);
} else {
str = str.substring(0, value)
+ str.substring(value + dict[i].length(),
str.length());
}
}
if (newLenth == length) {
return true;
}
} else {
break;
}
}
}
return false;
}
}
public class CheckKey {
public static void main(String[] args) {
Check check = new Check();
String[] dict = { "world", "hello", "super", "hell" };
System.out.println(check.checkIt(dict, "helloworld"));
}
}
def isKeyConcat(key, dictionary):
temp = ""
found = False
for letter in key:
temp = temp + letter
if temp in dictionary:
found = True
rest = key[len(temp):]
res = isKeyConcat(rest, dictionary)
if res:
return True
else:
pass
else:
found = False
return found
d = {"world", "hello", "super", "hell"}
print("helloworld: %s" % str(isKeyConcat("helloworld", d)))
print("superman: %s" % str(isKeyConcat("superman", d)))
print("hellohello: %s" % str(isKeyConcat("hellohello", d)))
I see that many people only considered to be only a concatenation of two words but the specifications states that can be composed of an arbitrary number of words in the dictionary.
public static boo l IsComposed(Hashset<string> dictionary, string word)
{
// Validate input
ValidateInput(dictionary, word);
// Call recursibly
return CoreIsComposed(dictionary, word, 0);
}
private static void ValidateInput(Hashset<string> dictionary, string word)
{
if(dictionary == null)
throw ArgumentNullException("dictionary");
if(string.IsNullOrEmpty(word)
throw ArgumentNull Exception("word");
}
private static bool CoreIsComposed(Hashset<string> dictionary, string word, int start)
{
if(word.Length == start) return true;
for(int i = start + 1; i < word.Length; i++)
{
if(IsWord(dictionary, word.Subsctring(start, i-start)) &&
CoreIsComposed(dictionary, word, start + 1))
{
return true;
}
}
return false;
}
private static bool IsWord(Hashset<string> dictionary, string word)
{
return dictionary.Contains(word);
}
For my solution, I stored the dictionary as a map of lists, where the key is the first letter of the word, and the list contains all the words that start with that letter.
Using the first letter in the input word, I grab the list from my map, and iterate until I find one that matches. If I find it, I recursively call the same function over the remainder of the input string, until there is no remainder left.
#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;
map<char, vector<string> > dict;
bool constructible(string word)
{
if (word.length() == 0)
return true;
vector<string> &list = dict[word[0]];
for (string &w : list)
{
if (word.compare(0, w.length(), w) == 0
&& constructible(word.substr(w.length())))
return true;
}
return false;
}
int main()
{
string dictinput[] = {"world","hello","super","hell"};
for (string str : dictinput)
{
dict[str[0]].push_back(str);
}
string input[] = {"helloworld","superman","hellohello"};
for (string str : input)
{
cout << str << " : " << constructible(str) << endl;
}
}
Output:
helloworld : 1
superman : 0
hellohello : 1
// construct the substring character by character from start to end, if we find a match, then check the remaining
// if the remaining doesn't match, we backtrack and continue
public static boolean doesExist(IDictionary dictionary, String key) {
return doesExist(dictionary, key, 0);
}
private static boolean doesExist(IDictionary dictionary, String key, int start) {
if(dictionary.contains(key)) return true;
for(int i = start; i < key.length(); i++) {
String subString = key.subString(start, i);
if(dictionary.exists(subString)) {
if(doesExist(dictionary, s, i + 1)) return true;
}
}
return false;
}
class Position
{
int indexTest,no;
Position(int indexTest,int no)
{
this.indexTest=indexTest;
this.no=no;
}
}
class RandomWordCombo
{
static boolean isCombo(String[] dict,String test)
{
HashMap<String,ArrayList<String>> dic=new HashMap<String,ArrayList<String>>();
Stack<Position> pos=new Stack<Position>();
for(String each:dict)
{
if(dic.containsKey(""+each.charAt(0)))
{
//System.out.println("=========it is here");
ArrayList<String> temp=dic.get(""+each.charAt(0));
temp.add(each);
dic.put(""+each.charAt(0),temp);
}
else
{
ArrayList<String> temp=new ArrayList<String>();
temp.add(each);
dic.put(""+each.charAt(0),temp);
}
}
Iterator it = dic.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pair = (Map.Entry)it.next();
System.out.println("key: "+pair.getKey());
for(String str:(ArrayList<String>)pair.getValue())
{
System.out.print(str);
}
}
pos.push(new Position(0,0));
while(!pos.isEmpty())
{
Position position=pos.pop();
System.out.println("position index: "+position.indexTest+" no: "+position.no);
if(dic.containsKey(""+test.charAt(position.indexTest)))
{
ArrayList<String> strings=dic.get(""+test.charAt(position.indexTest));
if(strings.size()>1&&position.no<strings.size()-1)
pos.push(new Position(position.indexTest,position.no+1));
String str=strings.get(position.no);
if(position.indexTest+str.length()==test.length())
return true;
pos.push(new Position(position.indexTest+str.length(),0));
}
}
return false;
}
public static void main(String[] st)
{
String[] dic={"world","hello","super","hell"};
System.out.println("is 'hellworld' a combo: "+isCombo(dic,"superman"));
}
}
Here is the C++ solution running in O(K^3), where K i s the length of the keyword.
#include <set>
#include <string>
#include <iostream>
using namespace std;
#include <set>
#include <string>
#include <iostream>
using namespace std;
bool find_words(set<string>& hashtable, string& target)
{
int next = INT_MIN;
set<string>::iterator iter;
if (target.length() == 0)
return true;
bool *m = new bool[target.length()+1];
m[0] = true;
for (int i = 0; i < target.length(); i++)
{ for (int j = i; j >=0; j--)
{
string sub = target.substr(j, i-j+1);
if (hashtable.find(sub) != hashtable.end())
{
if (m[j]) m[i+1] = true;
}
}
}
return m[target.length()]== true;
}
bool FindInDic(string* words, int N, string input)
{
set<string> hashtable;
for (int i =0; i <N; i++)
hashtable.insert(words[i]);
return find_words(hashtable, input);
}
static boolean findTwoConcatString (String [] listOfStrings , String str){
Set<String> set = new HashSet<>();
for (String s : listOfStrings){
set.add(s);
}
for(int i=1 ; i<str.length() ; i++){
String s1 = str.substring(0,i);
String s2 = str.substring(i);
if(set.contains(s1) && set.contains(s2)){
return true;
}
}
return false;
}
static boolean findTwoConcatString (String [] listOfStrings , String str){
Set<String> set = new HashSet<>();
for (String s : listOfStrings){
set.add(s);
}
for(int i=1 ; i<str.length() ; i++){
String s1 = str.substring(0,i);
String s2 = str.substring(i);
if(set.contains(s1) && set.contains(s2)){
return true;
}
}
return false;
}
static String[] dictionary = {"world", "hello", "super", "hell"};
public static boolean isConcatenation(String key) {
StringBuilder currentString = new StringBuilder();
for (int i = 0; i < key.length(); i++) {
currentString.append(key.charAt(i));
int dictIndex = 0;
boolean found = false;
while (!found && dictIndex < dictionary.length) {
if (dictionary[dictIndex].equals(currentString.toString())) {
found = true;
}
dictIndex++;
}
if (found) {
String restOfTheWord = key.substring(i + 1);
int dictIndex_2 = 0;
while (dictIndex_2 < dictionary.length) {
if (restOfTheWord.equals(dictionary[dictIndex_2])) {
return true;
}
dictIndex_2++;
}
}
}
return false;
}
def is_arb_concat_substring(lists, key):
for w in lista:
if w in key:
key = key.replace(w, "")
if "" == key:
return True
else:
return False
lista = ["world", "hello", "super", "hell"]
print is_arb_concat_substring(lista, "helloworld")
print is_arb_concat_substring(lista, "superman")
print is_arb_concat_substring(lista, "hellohello")
def is_arb_concat_substring(lists, key):
for w in lista:
if w in key:
key = key.replace(w, "")
if "" == key:
return True
else:
return False
lista = ["world", "hello", "super", "hell"]
print is_arb_concat_substring(lista, "helloworld")
print is_arb_concat_substring(lista, "superman")
print is_arb_concat_substring(lista, "hellohello")
Fully build able solution
#include <iostream>
#include <unordered_set>
using namespace std;
bool is_concat( string str, unordered_set<string> dict );
int main( int argc, char ** argv ){
string in("Ilovepancakesbaconeggswaffles");
unordered_set<string> dict({ "waffles", "pancakes", "bacon", "eggs", "love", "I" });
cout << is_concat( in, dict ) << endl;
return 0;
}
bool is_concat( string str, unordered_set<string> dict ){
bool found_match = false;
for( int i = 0; i < str.length(); ++i ){
for( const auto & word : dict ){
if( word[0] == str[i] ){
if(word == str.substr(i, word.length())){
cout << "word: " << word << "is in the string" << endl;
i += word.length() - 1;
found_match = true;
}
}
}
if(!found_match){
return false;
}
}
return true;
}
- SadBoy October 25, 2014