字符串分解的面试题
输入：一个字符串。
输出：提供一个isWord(string s)的函数，分解字符串到单词。
例子：
输入：thisisawesome.
输出: this is awe some
this is awesome
应为isWord(awe) = true， isWord(some)= tue, isWord(awesome)= true，所以有两个答案。
我在网上看到的个一个答案是用递归做的
string doit(string &s)
{
if(s.size() == 0 || isWord(s) = true)
{
return s;
}
for(int i = 0; i<s.size(); ++i)
{
string pre = s.substr(0, i);
if(isWord(pre))
{
string suf = doit(s.substr(i));
if(suf != string(""))
{ return pre + " " + suf; }
}
}
return string("");
}
In [25]: def isWord(s):
...: return s in ['this', 'is', 'awe', 'some', 'awesome']
In [26]: def doit3(s):
...: if len(s) == 0:
...: return ['']
...: result = []
...: for i in range(1, len(s)+1):
...: if isWord(s[:i]):
...: for suf in doit3(s[i:]):
...: result.append(s[:i] + ' ' + suf)
...: return result
In [27]: doit3('thisisawesome')
Out[27]: ['this is awe some ', 'this is awesome ']
}
}
}
