None Interview Question
StudentsCountry: India
Interview Type: Written Test
public static string SplitWords(string S, HashSet<string> words)
{
if(string.IsNullOrEmpty(S)
throw new ArgumentNullException("S can't be null");
List<string> result = new List<string>();
if(!CoreSplitWords(S, words, 0, result))
{
throw new ArgumentException("There are set of words);
}
return string.Join(' ', result);
}
private static bool CoreSplitWords(
string S,
HashSet<string> words,
int start,
List<int> result)
{
if(start == S.Length)
return true;
for(int i = start; i < S.Length; i++)
{
string value = S.Substring(start, i - start);
if(words.Contains(value))
{
result.Add(value);
if(CoreSplitWords(S, words, i + 1, result))
{
return true;
}
}
}
return false;
}
}
This problem can be solved by dynamic programming, with O(L.M) time and O(L) space, where L is the length of the input string, and M is the length of the longest word in the dictionary.
The dynamic programming idea is the same/similar to this Valid String problem, described in this link capacode.com/?p=285
My friend gives DP solution for checking valid string at the above link. Using the computed DP table, we can easily output the sentence itself.
Python recursive to find all possible combinations.
- CC February 25, 2015