何解? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

何解?

何解?# JobHunting - 待字闺中

T*82013-01-22 08:01

1 楼

You have a sentence with several words with spaces removed and the words
have their character order shuffled. You have a dictionary to lookup. Write
an algorithm to produce the original sentence back with spaces and words
with normal character order

j*y2013-01-22 08:01

2 楼

两个word之间不会 shuffled吧？感觉和anagram的题目有点类似，
产生的 original sentence可能不会唯一
vector > func(string s, int start)
{
vector > result;
if(start == s.length())
{
return result;
}
for(int i = start; i < s.length(); ++i)
{
vector word = anagramWordsInDictionary(s.substr(start,
i - start + 1));
if(word.size() > 0)
{
vector > tmp = func(s, i + 1);
if((i == s.length() - 1)
{
for(int j = 0; j < word.size(); ++j)
{
result.push_back(vector(1, word[j]));
}
}
if(tmp.size() > 0)
{
for(int j = 0; j < word.size(); ++j)
for(int k = 0; k < tmp.size(); ++k)
{
vector setence = tmp
[k];
sentence.insert(sentence.
begin(), word[j]);
result.push_back(sentence);
}
}
}
}
return result;
}

Write

【在 T*****8 的大作中提到】

: You have a sentence with several words with spaces removed and the words
: have their character order shuffled. You have a dictionary to lookup. Write
: an algorithm to produce the original sentence back with spaces and words
: with normal character order