CareerCup

I am thinking of backtracking solution to this problem.

private boolean smashable(String word, Stack<String> wordStack, Set<String> dictionary) {
	int wordLen = word.length();
	if (wordLen == 0) {
		wordStack.add(word);
		return true;
	}

	for (int i = 0; i < wordLen; i++) {
		String smashedWord = word.substring(0, i) + word.substring(i + 1);
		if (smashedWord.equals("") || dictionary.contains(smashedWord)) {
			wordStack.push(word);
			if (smashable(smashedWord, wordStack, dictionary))
				return true;
			else
				wordStack.pop();
		}
	}
	return false;
}


// Inside Main
if(smashable(word, wordStack, dictionary)) {
	System.out.println(wordStack.toString());
}
else {
	System.out.println("Not Smashable!!!");
}

def smashable(string, words):
    return dfs(string,words)

def dfs(string, words):
    print(string)
    if len(string) == 1:
        if string in words:
            return True
        else:
            return False
    for i in range(len(string)):
        curr_string = string[:i]+string[i+1:]
        if curr_string in words:
            return dfs(string[:i]+string[i+1:], words)

private static void smashableString(StringBuffer s) {
int i = 0;
while (!s.equals("")) {
if (s.length() - 1 == 0) {
System.out.println(" ");
return;
}
if (i > s.length() - 1) {
i = 0;
}
s.deleteCharAt(i);
System.out.println(s);
i++;
}

}

def f(s, d):
  h = set()
  l = [s]
  while l:
    i = l.pop()
    if len(i) == 1 and i in d:
      return True
    else:
      for j in range(len(i)):
        new = i[:j] + i[j+1:]
        if new in d and new not in h:
          l.append(new)
          h.add(new)
  return False

Instead of backtracking, its better to build solution bottoms up.
Start with all candidates that are 1-letter and present in the dict.
For each candidates with size i, see if you can build size i+1 candidate from the dict.
Keep repeating until you hit size = length(word)


Working solution:

private boolean solve(String word, String[] dict) {
        Map<Integer, List<String>> lengthToWordsMap = new HashMap<>();
        for (String s : dict) {
            addWordToDict(lengthToWordsMap, s);
        }
        addWordToDict(lengthToWordsMap, word);
        List<boolean[]> candidates = getCandidates(new boolean[word.length()], 1, word, lengthToWordsMap);

        for (int i = 2; i <= word.length(); i++) {
            if (candidates.isEmpty()) {
                break;
            }
            List<boolean[]> next = new ArrayList<>();
            for (boolean[] candidate : candidates) {
                next.addAll(getCandidates(candidate, i, word, lengthToWordsMap));
            }
            candidates = next;
        }
        for (boolean[] candidate : candidates) {
            boolean success = true;
            for (boolean b : candidate) {
                if (!b) {
                    success = false;
                    break;
                }
            }
            if (success) return true;
        }
        return false;
    }

    private void addWordToDict(Map<Integer, List<String>> lengthToWordsMap, String s) {
        List<String> list = lengthToWordsMap.getOrDefault(s.length(), new ArrayList<>());
        list.add(s);
        lengthToWordsMap.put(s.length(), list);
    }

    private List<boolean[]> getCandidates(boolean[] taken, int size, String word, Map<Integer, List<String>> lengthToWordsMap) {
        List<boolean[]> rv = new ArrayList<>();
        char[] arr = word.toCharArray();
        for (String candidate : lengthToWordsMap.getOrDefault(size, Collections.emptyList())) {
            boolean[] chosen = new boolean[word.length()];
            for (int i = 0; i < taken.length; i++) {
                chosen[i] = taken[i];
            }
            int candIdx = 0;
            for (int i = 0; i < chosen.length; i++) {
                if (arr[i] == candidate.charAt(candIdx)) {
                    chosen[i] = true;
                    candIdx++;
                }
                if (candIdx >= candidate.length()) {
                    break;
                }
            }
            int chosenIndices = 0;
            for (boolean b : chosen) {
                if (b) chosenIndices++;
            }
            if (candIdx == size && chosenIndices == size) {
                rv.add(chosen);
            }
        }
        return rv;
    }