KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
This is an interview question. Suppose you have a string text and a dictionary (a set of strings). How do you break down text into substrings such that each substring is found in the dictionary . For example you can break down "thisisatext" into ["this", "is", "a", "text"] using /usr/share/dict/words . I believe backtracking can solve this problem (in pseudo-Java): void solve(String s, Set<String> dict, List<String> solution) { if (s.length == 0) return for each prefix of s found in dict solve(s without prefix, dict, solution + prefix) } List<String> solution = new List<String>() solve(text, dict, solution) Does it make sense? Would you optimize the step of searching the prefixes in the dictionary? What data structures would you recommend?
Tags (comma-separated)
Save Edits
Cancel