Facebook Interview Question
Country: United States
This solution doesn't seem right to me. Shouldn't the hashmap also be a part of the state? How does this guarantee that DP[i] != -1 when the hashmap has different counts of strings?
I solved this problem in varies ways [ we can also use trie to solve this ]
public class BuildStringWordsInDictionary {
public static void main(String args[]) {
test1();
test2();
test3();
test4();
test5();
}
//false
private static void test5() {
String s = "abcabab";
HashMap<String, Integer> wordCount = new HashMap<>();
wordCount.put("abc", 3);
wordCount.put("ab", 1);
System.out.println("\nGiven String : " + s + " Expected output :" + false);
System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
}
//true
private static void test4() {
String s = "abcabab";
HashMap<String, Integer> wordCount = new HashMap<>();
wordCount.put("abc", 3);
wordCount.put("ab", 2);
System.out.println("\nGiven String : " + s + " Expected output :" + true);
System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
}
//false
private static void test3() {
String s = "abcx";
HashMap<String, Integer> wordCount = new HashMap<>();
wordCount.put("abc", 3);
wordCount.put("ab", 2);
wordCount.put("abca", 1);
System.out.println("\nGiven String : " + s + " Expected output :" + false);
System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
}
//true
private static void test1() {
String s = "abcabcabcabca";
HashMap<String, Integer> wordCount = new HashMap<>();
wordCount.put("abc", 3);
wordCount.put("ab", 2);
wordCount.put("abca", 1);
System.out.println("\nGiven String : " + s + " Expected output :" + true);
System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
}
//true
private static void test2() {
String s = "abcabcaabbc";
HashMap<String, Integer> wordCount = new HashMap<>();
wordCount.put("abc", 3);
wordCount.put("ab", 1);
wordCount.put("abca", 1);
System.out.println("\nGiven String : " + s + " Expected output :" + true);
System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
}
}
/**
* NOTE: Not working
*/
class SolutionBFSByStringWords {
public static boolean canBreak(String str, Map<String, Integer> wordCount) {
if (str.isEmpty())
return true;
return canBreakBFS(str, wordCount);
}
private static boolean canBreakBFS(String str, Map<String, Integer> wordCount) {
int n = str.length();
final Queue<Integer> queue = new LinkedList<>();
final Map<String, Integer> visited = new HashMap<>();
queue.offer(0);
while (!queue.isEmpty()) {
int start = queue.poll();
for (int i = start ; i < str.length(); i++) {
//Try this word : forward ->
String temp = str.substring(start, i + 1);
if (!visited.containsKey(temp))
visited.put(temp, 0);
//Check is this possible ?
if (wordCount.containsKey(temp) && wordCount.get(temp) > visited.get(temp)) {
visited.put(temp, visited.get(temp) + 1);
//if possible,the remove this string and recurse for rest of the string;
wordCount.put(temp, wordCount.get(temp) - 1);
//recurse for rest of the string;
queue.offer(i);
if (i == str.length())
return true;
}
}
}
return false;
}
}
/**
* This solution won't handle the cases when you can remove the word in-between and form a new workd by ends
* Example:
* s = "abcabcaabbc";
* {"abc": 3, "ab": 1, "abca": 1}
* <p>
* Your code produce False where it is possible ;
* abcabcaabbc -> aabbc [remove two "abc"] {"abc": 1, "ab": 1, "abca": 1}
* aabbc -> abc [remove one "ab" ] {"abc": 1, "ab": 0, "abca": 1} [**** This is not supported ***]
* abc -> "" [ remove one "abc" ] {"abc": 0, "ab": 1, "abca": 1}
*/
class SolutionDFSByStringWords {
/**
* DFS 1:
* By keeping the index of recursion
*
* @param str
* @param wordCount
* @return
*/
public static boolean canBreak(String str, Map<String, Integer> wordCount) {
if (str.isEmpty())
return true;
return canBreakRec(str, wordCount, 0);
}
/**
* Keep taking a sub-string from given string specified by "start" index and keep checking does this is possible break
* which leads to a solution
*
* @param str
* @param wordCount
* @param start
* @return
*/
private static boolean canBreakRec(String str, Map<String, Integer> wordCount, int start) {
//If we have remove all the chars, then success
if (start == str.length())
return true;
for (int i = start; i < str.length(); i++) {
//Try this word : forward ->
String temp = str.substring(start, i + 1);
//Check is this possible ?
if (wordCount.getOrDefault(temp, -1) > 0) {
//if possible,the remove this string and recurse for rest of the string;
wordCount.put(temp, wordCount.get(temp) - 1);
//recurse for rest of the string;
if (canBreakRec(str, wordCount, i + 1)) {
return true;
}
//Couldn't find the solution, backtrack
wordCount.put(temp, wordCount.get(temp) + 1);
}
}
return false;
}
/**
* DFS 2
* By breaking string into sub-strings
*
* @param word
* @param map
* @return
*/
public static boolean wordBreak(String word, Map<String, Integer> map) {
int len = word.length();
if (len <= 0) return true;
for (int i = 1; i < len + 1; i++) {
String a = word.substring(0, i);
Integer I = map.get(a);
if (I == null || I <= 0)
continue;
map.put(a, I - 1);
if (i <= len && wordBreak(word.substring(i, len), map))
return true;
map.put(a, I);
}
return false;
}
}
class SolutionDFSByMapWords {
public static boolean canBreak(String str, Map<String, Integer> wordCount) {
if (str.isEmpty())
return true;
return canBreakRec(str, wordCount);
}
/**
* DFS the tree.
* check using current count in map of a word, does string can be broken ?
* if yes, then decrease the number of counts and recurse for further. Try all
*
* @param str
* @param wordCount
* @return
*/
private static boolean canBreakRec(String str, Map<String, Integer> wordCount) {
if (str.isEmpty())
return true;
/**
* find all the keys present in str and remove them as many times as said
*/
for (String key : wordCount.keySet()) {
int count = wordCount.get(key);
//Can we still use this word from dict?
if (count > 0) {
int oldCount = count;
String oldString = str;
//Find and remove the occurrence
while (str.contains(key) && count > 0) {
str = str.replaceFirst(key, "");
count--;
}
//if we tried to remove but no occurrence found for given key in string, then continue to next word in map
if (count == wordCount.get(key))
continue;
else {
//decrease the count of occurrence
wordCount.put(key, count);
//Recurse
if (canBreakRec(str, wordCount)) {
return true;
}
//Put back: Backtrack
str = oldString;
wordCount.put(key, oldCount);
}
}
}
return false;
}
}
Your second example is incorrect (abcabab : ['abc', 'ab', 'ab']). You did
not mention that not all words/occurencies need to be exhausted.
def SplitSubstring(s, n, word_fr, curr_split):
if n == len(s):
print("%s : %s" % (s, curr_split))
return
for i in range(n, len(s)):
ss = s[n:i+1]
if ss in word_fr and word_fr[ss] > 0:
word_fr[ss] -= 1
curr_split.append(ss)
SplitSubstring(s, i + 1, word_fr, curr_split)
curr_split.pop()
word_fr[ss] += 1
word_fr = {"abc":3, "ab":2, "abca":1}
SplitSubstring("abcabcabcabca", 0, word_fr, [])
SplitSubstring("abcx", 0, word_fr, [])
word_fr = {"abc":3, "ab":2}
SplitSubstring("abcabab", 0, word_fr, [])
import java.util.*;
public class BreakWord{
static boolean ans = false;
public static void main(String[] args){
Map<String, Integer> map = new HashMap<>();
//map.put("abc", 3);
//map.put("ab", 2);
//map.put("abca", 1);
map.put("abc", 3);
map.put("ab", 2);
String str = "abcabcabcabca";
//String str = "abcabab";
Set<String> set = new HashSet<>();
for(String s : map.keySet()){
set.add(s);
}
dfs(map, set, str, 0);
System.out.println(ans);
}
public static void dfs(Map<String, Integer> map, Set<String> set, String str, int start){
if(start == str.length()){
ans = true;
return;
}
for(int i=start; i<str.length(); i++){
String ss = str.substring(start, i+1);
if(!set.contains(ss))
continue;
if(map.get(ss) == 0){
continue;
}
map.put(ss, map.get(ss)-1);
dfs(map, set, str, i+1);
map.put(ss, map.get(ss)+1);
}
}
}
Not sure if this is optimal, but here is a DP solution that requires what is likely a significant amount of space.
DP Solution:
T[i,j,k,l] = True if there is a partition of S[i..j] using the i^th substring at most k times.
If T[i,j,k,l] is true, then some substring must be a prefix of S[i..j], so just check all possible prefixes.
Fill in table in increasing order of abs(i-j), and increasing order of k and l.
Recursive solution:
#include <iostream>
using namespace std;
struct dict
{
string w;
int c;
};
// To execute C++, please define "int main()"
bool findwords(string str,dict d[],string& words)
{
if (str.length()==0)
return true;
else
for (int wo=0;wo<3;wo++)
{
int d_length=d[wo].w.length();
//cout<<str.substr(0,d_length)<<endl;
if (str.substr(0,d_length) == d[wo].w )
{
//d[wo].c--;
if (findwords(str.substr(d_length,str.length()),d,words))
{
// cout<<d[wo].w<<" ";
d[wo].c--;
if (d[wo].c>=0)
{
words=d[wo].w+" "+words;
return true;
}
}
//d[wo].c++;
}
}
return false;
}
int main() {
dict d[3];
d[0].w="abc";
d[1].w="ab";
d[2].w="abca";
d[0].c=2;
d[1].c=2;
d[2].c=1;
string words;
if (findwords("abcaababcab",d,words))
cout<<"True"<< " "<<words<<endl;
else
cout << "No Words Found"<<endl;
//cout<<words<<endl;
return 0;
}
Recursive Solution
#include <iostream>
using namespace std;
struct dict
{
string w;
int c;
};
// To execute C++, please define "int main()"
bool findwords(string str,dict d[],string& words)
{
if (str.length()==0)
return true;
else
for (int wo=0;wo<3;wo++)
{
int d_length=d[wo].w.length();
//cout<<str.substr(0,d_length)<<endl;
if (str.substr(0,d_length) == d[wo].w )
{
//d[wo].c--;
if (findwords(str.substr(d_length,str.length()),d,words))
{
// cout<<d[wo].w<<" ";
d[wo].c--;
if (d[wo].c>=0)
{
words=d[wo].w+" "+words;
return true;
}
}
//d[wo].c++;
}
}
return false;
}
int main() {
dict d[3];
d[0].w="abc";
d[1].w="ab";
d[2].w="abca";
d[0].c=2;
d[1].c=2;
d[2].c=1;
string words;
if (findwords("abcaababcab",d,words))
cout<<"True"<< " "<<words<<endl;
else
cout << "No Words Found"<<endl;
//cout<<words<<endl;
return 0;
}
You could flatten out the hash map and then generate the power set. Then map each element in the power set to an array of permutations of the original array that are then joined together as strings.
Then collect all of these generated strings, this is your solution space. Check if the input exists in the space.
here's my VS 2019 C# entry
static List<string> l = new List<string>( );
static Dictionary<string,int> dict = new Dictionary<string, int>( );
static void FindString( string szFind, int szFindLen, List<string> szRemainingWords, ref bool bFound, ref string szOut )
{
if( szFind == "" )
{
bFound = true;
return;
}
string szOutOriginal = szOut;
for( int i = 0 ; i < szRemainingWords.Count ; i++ )
{
string s = szRemainingWords[i];
if ( szFind.StartsWith( s ) )
{
szOut += s + " ";
int len = s.Length;
szRemainingWords [i] = "*" + szRemainingWords [i];
FindString( szFind.Substring( len ), szFindLen - len, szRemainingWords, ref bFound, ref szOut );
szRemainingWords [i] = szRemainingWords [i].Substring( 1 );
if ( bFound )
{
break;
}
}
}
if( !bFound )
{
szOut = szOutOriginal;
}
}
static bool DoesWordAppearNTimes( string szWholeString, string szFindWord, int n )
{
int offset = 0;
while ( n > 0 )
{
int i = szWholeString.Substring( offset ).IndexOf( szFindWord );
if ( i == -1 )
{
return false;
}
offset = i;
n--;
}
return true;
}
static void Main( string [] args )
{
l.Add( "abc" );
l.Add( "abc" );
l.Add( "abc" );
l.Add( "ab" );
l.Add( "ab" );
l.Add( "abca" );
dict.Add( "abc", 3 );
dict.Add( "ab", 2 );
dict.Add( "abca", 1 );
bool bFound = false;
string szOut = "";
string szFind = "abcabab";
FindString( szFind, szFind.Length, l, ref bFound, ref szOut);
if ( bFound )
{
foreach ( KeyValuePair<string, int> kvp in dict )
{
if( !DoesWordAppearNTimes( szFind, kvp.Key, kvp.Value ) )
{
bFound = false;
break;
}
}
}
Console.WriteLine( "Find = " + szFind + ", found = " + bFound.ToString( ) + ", string = " + szOut );
}
bool break1(string& s, std::unordered_map<string, int>& countMap) {
int size = s.size();
std::unordered_map<int, vector<vector<string>>> table;
for (int i = 0; i < size; ++i) {
vector<vector<string>> entry;
for (int j = 0; j <= i; ++j) {
//"abcabcabcabababca"
string str1 = s.substr(0, j);
string str2 = s.substr(j, i - j + 1);
if (j == 0) {
if (countMap.find(str2) != countMap.end()) {
vector<string> vec1;
vec1.push_back(str2);
entry.push_back(vec1);
}
}
else {
if (table[j-1].size() > 0 && countMap.find(str2) != countMap.end()) {
for (auto iter = table[j-1].begin(); iter != table[j-1].end(); ++iter) {
auto vec = *iter;
vec.push_back(str2);
entry.push_back(vec);
}
}
}
// else {
// if (countMap.find(str2) != countMap.end()) {
// vector<string> vec;
// vec.push_back(str2);
// entry.push_back(vec);
// }
// }
}// for (int j = 0; j <= i; ++j)
table[i] = entry;
}// for (int i = 0; i < size; ++i)
for (auto iter = table.begin(); iter != table.end(); ++iter) {
int i = iter->first;
vector<vector<string>> entry = iter->second;
if (entry.size() > 0) {
std::cout << "index is " << i << "\n";
}
for (auto iter1 = entry.begin(); iter1 != entry.end(); ++iter1) {
for (auto iter2 = (*iter1).begin(); iter2 != (*iter1).end(); ++iter2) {
std::cout << *iter2 << "\t";
}
std::cout << "\n";
}
std::cout << "\n";
}
vector<vector<string>> solutions = table[size - 1];
while (solutions.size() > 0) {
auto copyCountMap = countMap;
vector<string> vec = solutions.back();
solutions.pop_back();
for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
copyCountMap[*iter]--;
if (copyCountMap[*iter] == 0) copyCountMap.erase(*iter);
}
if (copyCountMap.size() == 0) return true;
}
return false;
}
const myFunc = (str, strMap) => {
let origStr = str;
let outputArray = [];
let mapArray = [];
// create subArrays of hashmaps
for (let key in strMap) {
let count = strMap[key];
let tokenArray = [...Array(count)].map((_, i) => key);
mapArray.push(tokenArray);
}
// order arrays by subArray length
const sortedArrays = mapArray.sort((a, b) => {
return b.length - a.length;
});
// check for matches
for(let hashArray of sortedArrays) {
let pattern = hashArray.join('');
if (str.includes(pattern)) {
outputArray = outputArray.concat(hashArray);
str = str.replace(pattern, '');
}
}
// format output
if (str.length ===0 && outputArray.length > 0) {
return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: Yes;[${outputArray}]`;
} else {
return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: No`;
}
}
let string = 'abcabcabcabca'
let stringMap = {
'abc': 3,
'ab': 2,
'abca': 1
}
console.log(myFunc('abcabcabcabca', {'abc':3, 'ab':2, 'abca':1}));
console.log(myFunc('abcabab', {'abc':3, 'ab':2}));
console.log(myFunc('abcx', {'abc':3, 'ab':2, 'abca':1}));
const myFunc = (str, strMap) => {
let origStr = str;
let outputArray = [];
let mapArray = [];
// create subArrays of hashmaps
for (let key in strMap) {
let count = strMap[key];
let tokenArray = [...Array(count)].map((_, i) => key);
mapArray.push(tokenArray);
}
// order arrays by subArray length
const sortedArrays = mapArray.sort((a, b) => {
return b.length - a.length;
});
// check for matches
for(let hashArray of sortedArrays) {
let pattern = hashArray.join('');
if (str.includes(pattern)) {
outputArray = outputArray.concat(hashArray);
str = str.replace(pattern, '');
}
}
// format output
if (str.length ===0 && outputArray.length > 0) {
return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: Yes;[${outputArray}]`;
} else {
return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: No`;
}
}
let string = 'abcabcabcabca'
let stringMap = {
'abc': 3,
'ab': 2,
'abca': 1
}
console.log(myFunc('abcabcabcabca', {'abc':3, 'ab':2, 'abca':1}));
console.log(myFunc('abcabab', {'abc':3, 'ab':2}));
console.log(myFunc('abcx', {'abc':3, 'ab':2, 'abca':1}));
const myFunc = (str, strMap) => {
let origStr = str;
let outputArray = [];
let mapArray = [];
// create subArrays of hashmaps
for (let key in strMap) {
let count = strMap[key];
let tokenArray = [...Array(count)].map((_, i) => key);
mapArray.push(tokenArray);
}
// order arrays by subArray length
const sortedArrays = mapArray.sort((a, b) => {
return b.length - a.length;
});
// check for matches
for(let hashArray of sortedArrays) {
let pattern = hashArray.join('');
if (str.includes(pattern)) {
outputArray = outputArray.concat(hashArray);
str = str.replace(pattern, '');
}
}
// format output
if (str.length ===0 && outputArray.length > 0) {
return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: Yes;[${outputArray}]`;
} else {
return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: No`;
}
}
let string = 'abcabcabcabca'
let stringMap = {
'abc': 3,
'ab': 2,
'abca': 1
}
console.log(myFunc('abcabcabcabca', {'abc':3, 'ab':2, 'abca':1}));
console.log(myFunc('abcabab', {'abc':3, 'ab':2}));
console.log(myFunc('abcx', {'abc':3, 'ab':2, 'abca':1}));
This is my solution
It has a complexity of O(H * CK) where H is the number of the items in the given hash key and CK is the maximum number of words frequency across all the hashes
let inputString = 'abcabcabcabca';
var validationHash = { "abc": 3, "ab": 2, "abca": 1 };
const breakTheStringIntoWords = (inputString, validationHash) => {
var replacer = '';
var words = [], tempWords = [], ii;
Object.keys(validationHash).map(compareKey => {
replacer = '';
tempWords = [];
for (ii = 0; ii < validationHash[compareKey]; ii++) {
tempWords.push(compareKey);
replacer += compareKey;
}
if (inputString.indexOf(replacer) > -1) {
inputString = inputString.replace(replacer, '');
words = words.concat(tempWords);
tempWords = [];
}
});
if (inputString.trim() === '') {
return words;
} else {
return [];
}
};
const returnedWords = breakTheStringIntoWords(inputString, validationHash);
if(returnedWords.length > 0){
console.log('Yes;', returnedWords);
} else {
console.log('No');
}
def wordcheck(str,hash):
result = {}
for k,v in hash.items():
x = len(k)
word_count=0
for i in range(len(str)):
if str[i:x+i] == k:
word_count +=1
if word_count == v:
result[k] = word_count
if result == hash:
return True
else:
return False
hash = {'abc':3,'ab':2,'abca':1}
str = 'abcabcabcabca'
print(wordcheck(str,hash))
hash = {"abc":3, "ab":2}
str= 'abcabab'
print(wordcheck(str,hash))
hash = {"abc":3, "ab":2, "abca":1}
str= 'abcx'
print(wordcheck(str,hash))
Simple Solution C#: (Tested)
public bool CanBreak(string s, Dictionary<string, int> frequency)
{
string temp = s;
foreach (string word in frequency.Keys)
{
int count = 0;
int index = 0;
temp = s;
while (index >= 0 && count <= frequency[word])
{
index = temp.IndexOf(word);
if (index == -1)
{
return false;
}
count++;
temp = s.Substring(index + word.Length - 1);
}
}
return true;
}
def canBrekaString(str1, hash_map):
# try to divide the string into all possible words and check if those words exists in the hash_map or not
#print(str1,hash_map)
if not str1:
return True
for i in range(1,len(str1)+1):
# part part of string is 0-->i, and second part is i-->n
if str1[0:i] in hash_map and hash_map[str1[0:i]]>0:
hash_map[str1[0:i]] -= 1
canBreak = canBrekaString(str1[i:len(str1)], hash_map)
if canBreak:
return True
# backtrck
hash_map[str1[0:i]] += 1
return False
static boolean checkString(String str, Map<String, Integer> map) {
Map<String, Integer> temp = new HashMap<String, Integer>(map);
for (Map.Entry<String, Integer> en : map.entrySet()) {
int len = en.getKey().length();
int i = 0, k = len;
while (k < str.length()) {
String sub = str.substring(i, k);
if (en.getKey().equals(sub)) {
temp.put(sub, temp.get(sub) - 1);
i = k;
k = k + len;
} else {
i++;
k++;
}
if (temp.get(en.getKey()) < 1) {
temp.remove(en.getKey());
break;
}
}
if (temp.containsKey(en.getKey()) && temp.get(en.getKey()) > 0) {
return false;
}
}
if (!temp.isEmpty()) {
return false;
}
return true;
}
function formWord(hashMap, str) {
let wordArr = [];
let remainingOriginalStr = str;
for (let key in hashMap) {
console.log('remainingOriginalStr', remainingOriginalStr);
const tempRemainingStr = remainingOriginalStr;
const count = hashMap[key]; // 3
let c = 0;
while (c < count) {
if (!remainingOriginalStr.includes(key)) {
console.log('--remainingOriginalStr', remainingOriginalStr);
console.log('key', key);
// return 'No';
remainingOriginalStr = tempRemainingStr;
break;
}
const indexOfSubStr = remainingOriginalStr.indexOf(key);
remainingOriginalStr = remainingOriginalStr.slice(indexOfSubStr + key.length);
c++;
}
if (c === count) {
const wordCountArr = new Array(count).fill(key);
wordArr = [...wordArr, ...wordCountArr];
}
}
return wordArr;
}
const str = 'abcabcabcabca';
const hashMap = {"abc":3, "ab":2, "abca":1};
const result = formWord(hashMap, str)
console.log('result', result);
function formWord(hashMap, str) {
let wordArr = [];
let remainingOriginalStr = str;
for (let key in hashMap) {
console.log('remainingOriginalStr', remainingOriginalStr);
const tempRemainingStr = remainingOriginalStr;
const count = hashMap[key]; // 3
let c = 0;
while (c < count) {
if (!remainingOriginalStr.includes(key)) {
console.log('--remainingOriginalStr', remainingOriginalStr);
console.log('key', key);
// return 'No';
remainingOriginalStr = tempRemainingStr;
break;
}
const indexOfSubStr = remainingOriginalStr.indexOf(key);
remainingOriginalStr = remainingOriginalStr.slice(indexOfSubStr + key.length);
c++;
}
if (c === count) {
const wordCountArr = new Array(count).fill(key);
wordArr = [...wordArr, ...wordCountArr];
}
}
return wordArr;
}
const str = 'abcabcabcabca';
const hashMap = {"abc":3, "ab":2, "abca":1};
const result = formWord(hashMap, str)
console.log('result', result);
// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []
function findLongestPrefix(str, index, dict, maxPrefixLen) {
var dictCopy = Object.assign({}, dict);
if (index >= str.length)
return [];
for (var i = maxPrefixLen; i > 0; i--) {
var candidate = str.substr(index, i);
if (dictCopy[candidate]) {
dictCopy[candidate]--;
try {
var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
return [candidate].concat(rest);
} catch(err) {
dictCopy[candidate]++;
}
}
}
throw error('E_INVALID_CHARS')
}
function breakWords(str, dict) {
// Get the max lengths of keys
var keys = Object.keys(dict);
var maxPrefixLen = 1;
for (var i = 0; i < keys.length; i++ ) {
if (keys[i].length > maxPrefixLen) {
maxPrefixLen = keys[i].length;
}
}
try {
return findLongestPrefix(str, 0, dict, maxPrefixLen)
} catch(error) {
return []
}
}
var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)
words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)
words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)
words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)
// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []
function findLongestPrefix(str, index, dict, maxPrefixLen) {
var dictCopy = Object.assign({}, dict);
if (index >= str.length)
return [];
for (var i = maxPrefixLen; i > 0; i--) {
var candidate = str.substr(index, i);
if (dictCopy[candidate]) {
dictCopy[candidate]--;
try {
var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
return [candidate].concat(rest);
} catch(err) {
dictCopy[candidate]++;
}
}
}
throw error('E_INVALID_CHARS')
}
function breakWords(str, dict) {
// Get the max lengths of keys
var keys = Object.keys(dict);
var maxPrefixLen = 1;
for (var i = 0; i < keys.length; i++ ) {
if (keys[i].length > maxPrefixLen) {
maxPrefixLen = keys[i].length;
}
}
try {
return findLongestPrefix(str, 0, dict, maxPrefixLen)
} catch(error) {
return []
}
}
var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)
words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)
words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)
words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)
// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []
function findLongestPrefix(str, index, dict, maxPrefixLen) {
var dictCopy = Object.assign({}, dict);
if (index >= str.length)
return [];
for (var i = maxPrefixLen; i > 0; i--) {
var candidate = str.substr(index, i);
if (dictCopy[candidate]) {
dictCopy[candidate]--;
try {
var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
return [candidate].concat(rest);
} catch(err) {
dictCopy[candidate]++;
}
}
}
throw error('E_INVALID_CHARS')
}
function breakWords(str, dict) {
// Get the max lengths of keys
var keys = Object.keys(dict);
var maxPrefixLen = 1;
for (var i = 0; i < keys.length; i++ ) {
if (keys[i].length > maxPrefixLen) {
maxPrefixLen = keys[i].length;
}
}
try {
return findLongestPrefix(str, 0, dict, maxPrefixLen)
} catch(error) {
return []
}
}
var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)
words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)
words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)
words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)
DP solution similar to Word break maintaining Map with count
- shaktirajpandey1996 August 29, 2019/* * Break string into the word provided by given hashmap * Ex:1 * HashMap: {"abc":3, "ab":2, "abca":1} * Word: abcabcabca * Output: true * */ #include <bits/stdc++.h> using namespace std; string s; map<string, int> HashMap; int DP[11111]; bool solve(int id) { if(id >= s.size()) { return true; } if(DP[id] != -1) { return DP[id]; } int ans = false; for(int i = 1; i <= s.size() - id; i++) { string temp = s.substr(id, i); // If found if(HashMap.find(temp) != HashMap.end()) { if(HashMap[temp] != 0) { HashMap[temp]--; ans = ans | solve(id + i); HashMap[temp]++; } } if(ans == true) { DP[id] = ans; return DP[id]; } } return DP[id] = ans; } int main() { cin >> s; memset(DP, -1, sizeof DP); // Create HashMap of size N int N; cin >> N; for(int i = 0; i < N; i++) { string t; int cnt; cin >> t >> cnt; HashMap[t] = cnt; } cout << solve(0); }