e**********6
发帖数: 78 | 1 有一个String里面的词被scrambled了，而且空格被删除。给你一个单词列表，让还原
String以前的形态。
input: hlleowlord
list of words: hello, world, hi, dog, cat
output: hello world
刚开始想sort，然后用hashtable。但后来发现sort input的话单词就混在一起了，根
本找不到words。比如变成：dehllloorw。
有什么高效率的好方法吗？ | t*****j
发帖数: 1105 | 2 整合成字符数数组，排除，然后DP + tries
【在 e**********6 的大作中提到】
: 有一个String里面的词被scrambled了，而且空格被删除。给你一个单词列表，让还原
: String以前的形态。
: input: hlleowlord
: list of words: hello, world, hi, dog, cat
: output: hello world
: 刚开始想sort，然后用hashtable。但后来发现sort input的话单词就混在一起了，根
: 本找不到words。比如变成：dehllloorw。
: 有什么高效率的好方法吗？
| s*******e
发帖数: 93 | 3 因为只是词被打乱，空格被删除，没有打乱整个词组，所以我想到的做法是
(应该可以work,但是可能效率不是最高的)
bool equals(string s1, string s2);
string firstNString(string s, int count);
string substringFromIndex(string input, int index);
string sort(string);
(以上几个function应该可以意会，就不implement了)
bool beginsWith(string input, string word)
{
return equals(sort( firstNString(input,word.length) ) , sort(word) );
}
struct result
{
string str;
bool ok;
}
typedef struct result Result;
Result function(string input, string[] words)
{
found=false;
str="";
for each (word in words)
{
if( equals(input, word) )
{
Result r; r.str=word; r.ok=true;
return r;
}
if( beginsWith(input, word) )
{
string newInput = substringFromIndex(input, word.length);
Result r=function(newInput,words);
if(r.ok==true)
{
str = word+" "+r.str;
found=true;
break;
}
}
}
Result r;
r.str=str;
r.ok=found;
return r;
}
有没有大牛愿意帮忙检查下？
比如input是
hlleowrold
list是 hll, eow, rol, hell, hello, worl, world | y*******n
发帖数: 129 | 4 能不能具体一点呢？如何用trie？
【在 t*****j 的大作中提到】
: 整合成字符数数组，排除，然后DP + tries
| s*******t
发帖数: 248 | 5 我觉得可以这样解
list of words, 用hashtable存， signature + corresponding word. signature 为s
orted corresponding word，
然后对input，iterate from o.. length, maintain,一个 word_begin and word_end
pointer， if the string between word_begin and word_end 跟 signature 相同，
then output corrseponding word, and update word_begin and word_end.
【在 e**********6 的大作中提到】
: 有一个String里面的词被scrambled了，而且空格被删除。给你一个单词列表，让还原
: String以前的形态。
: input: hlleowlord
: list of words: hello, world, hi, dog, cat
: output: hello world
: 刚开始想sort，然后用hashtable。但后来发现sort input的话单词就混在一起了，根
: 本找不到words。比如变成：dehllloorw。
: 有什么高效率的好方法吗？
| d****j
发帖数: 293 | 6 可以转化为解多元方程的问题.
假设x1 is 'a', x2 is 'b', ..., x26 is 'z',这个问题就变成：
给定：
hello--> 1*x8 + 1*x5 + 2*x12 + 1 * x15 = 1
hi --> 1*x8 + 1*x9 = 1
...
求解: hlleowlord-->
1*x8 + 3*x12+1*x5+...... = ?
当然并不是真正要解出每个xi，而是要用已知方程式组合出求解的式子。
能变成矩阵的什么相关通用问题了？数学达人解决一下？
不行的话，就只好用DP+backtrack+heuristics策略来匹配这些系数，如何？ | a****s
发帖数: 559 | 7 如果list of words是：
hello, world, hi, dog, hell, owl, rod, cat
原来的String不唯一。
【在 e**********6 的大作中提到】
: 有一个String里面的词被scrambled了，而且空格被删除。给你一个单词列表，让还原
: String以前的形态。
: input: hlleowlord
: list of words: hello, world, hi, dog, cat
: output: hello world
: 刚开始想sort，然后用hashtable。但后来发现sort input的话单词就混在一起了，根
: 本找不到words。比如变成：dehllloorw。
: 有什么高效率的好方法吗？
| f***g
发帖数: 214 | 8 先预处理下那串字符串，存在一个int[26]，记录每个字母出现的次数。如果有大小写
或者其他字符，最多也就int[256].
然后对于那个list of candidate words, 一个一个的试，每一个单词就从计数数组中
减去那个单词相应的字符。例如，单词是hi,则int['h']--, int['i']--.
如果计数数组为空，输出结果，否则递归试下一个单词。
这样可以列出所有可能性。 | g*****e
发帖数: 282 | 9 pls notice that the order of words never change but the chars shuffled. your
solution would provide more output.
【在 f***g 的大作中提到】
: 先预处理下那串字符串，存在一个int[26]，记录每个字母出现的次数。如果有大小写
: 或者其他字符，最多也就int[256].
: 然后对于那个list of candidate words, 一个一个的试，每一个单词就从计数数组中
: 减去那个单词相应的字符。例如，单词是hi,则int['h']--, int['i']--.
: 如果计数数组为空，输出结果，否则递归试下一个单词。
: 这样可以列出所有可能性。
| c***2
发帖数: 838 | 10 input: hlleowlord
list of words: hello, world, hi, dog, cat
1) remove all chars of a word from string (only the first one for duplicates)
2) check whether leftover is an anagram of word list
3) repeat if necessary
remove hello from hlleowlord, you get wlord, which is anagram of world.
done. | | | f***g
发帖数: 214 | 11 谢谢
继续想
your
【在 g*****e 的大作中提到】
: pls notice that the order of words never change but the chars shuffled. your
: solution would provide more output.
| c*********7
发帖数: 19373 | 12 对比字典内每个word看能否由input组成，得到一组candidate。然后从candidate里边
找组合正好等于input的。 | r******d
发帖数: 308 | 13 (1)找出所有anagram of word list， 放到一个trie里面
(2)从input的第一个字母， 一级一级在trie里面找， 找到hlleo之后再从新从trie的
root往下查
duplicates) | s****u
发帖数: 1433 | 14 可以这样，
选定一个单词，将句子中所有含有此单词的字母置换为0.
从句子中找到最长的连续为0的字符串。
如果字符串长度少于单词长度，则此单词不存在；
若等于，则递归计算句子前面部分和后面部分；
若字符串长度大于单词长度，就比较麻烦，要分拆计算直到
各个部分都MATCH。
这个问题其实特殊情况还是很多的。
比如句子如果是 DOG EAT RABIT。 但是单词除了这仨以外还包括
GREAT， BAT， GATE。那么你必须递归到各个部分都MATCH且没有
剩余字符才算成功。 | j******4
发帖数: 116 | 15 这个题不就是用anagram做sentence breaker 吗？
| g*****e
发帖数: 282 | 16 都看了一遍，其实只是改进了的brute search。文本一大复杂度就不得了了。有更好的
方法么？
【在 s****u 的大作中提到】
: 可以这样，
: 选定一个单词，将句子中所有含有此单词的字母置换为0.
: 从句子中找到最长的连续为0的字符串。
: 如果字符串长度少于单词长度，则此单词不存在；
: 若等于，则递归计算句子前面部分和后面部分；
: 若字符串长度大于单词长度，就比较麻烦，要分拆计算直到
: 各个部分都MATCH。
: 这个问题其实特殊情况还是很多的。
: 比如句子如果是 DOG EAT RABIT。 但是单词除了这仨以外还包括
: GREAT， BAT， GATE。那么你必须递归到各个部分都MATCH且没有
| A*H
发帖数: 127 | 17 use hash functions
1. hash input string get sum
2. hash list of words, sort and get array
3. search in array for sum
【在 e**********6 的大作中提到】
: 有一个String里面的词被scrambled了，而且空格被删除。给你一个单词列表，让还原
: String以前的形态。
: input: hlleowlord
: list of words: hello, world, hi, dog, cat
: output: hello world
: 刚开始想sort，然后用hashtable。但后来发现sort input的话单词就混在一起了，根
: 本找不到words。比如变成：dehllloorw。
: 有什么高效率的好方法吗？
| y*******n
发帖数: 129 | 18 store list of words in hashtable
key: signature
value: list of words with the same signature.
recurse on input to find solution
code:
typedef std::map > Dict;
typedef std::map >::iterator DictIter;
void descramble(const std::string& input, std::string& output, Dict& dict) {
if (input.empty()) {
std::cout << output << std::endl;
} else {
for (size_t i=1; i<=input.size(); i++) {
std::string prefix = input.substr(0, i);
std::string sig = prefix;
std::sort(sig.begin(), sig.end());
DictIter iter = dict.find(sig);
if (iter != dict.end()) {
// only take the first one
if (!output.empty()) { output += " "; }
output += (iter->second).front();
descramble(input.substr(i), output, dict);
}
}
}
}
为s
end
，
【在 s*******t 的大作中提到】
: 我觉得可以这样解
: list of words, 用hashtable存， signature + corresponding word. signature 为s
: orted corresponding word，
: 然后对input，iterate from o.. length, maintain,一个 word_begin and word_end
: pointer， if the string between word_begin and word_end 跟 signature 相同，
: then output corrseponding word, and update word_begin and word_end.
|
|
