由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 一道有关String的面试题
相关主题
一道G家店面题F家电面:group Anagrams
LC: anagram为何忽略single element?问个anagram的问题
关于leetcode的Scramble String问题发一个fb面经
菜鸟的问题:Given a string, find whether it has any permutation of another stringAmazon 面经
Dream company Onsite被搞了(少量面经)LC anagrams题目有问题吧?
感觉这是一道经典题string scramble 的时间复杂度
请问我写的这个代码哪可以改进一下Leetcode Scramble String简单解法
代码求助狗家面经
相关话题的讨论汇总
话题: string话题: std话题: word话题: input话题: words
1 (共1页)
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家电面:group Anagrams
请问我写的这个代码哪可以改进一下问个anagram的问题
代码求助发一个fb面经
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.

1 (共1页)
相关主题
狗家面经Dream company Onsite被搞了(少量面经)
GOOG intern interview 题目感觉这是一道经典题
【一个BB公司问的字母排序的问题】请问我写的这个代码哪可以改进一下
今天G家电面的一道题代码求助
一道G家店面题F家电面:group Anagrams
LC: anagram为何忽略single element?问个anagram的问题
关于leetcode的Scramble String问题发一个fb面经
菜鸟的问题:Given a string, find whether it has any permutation of another stringAmazon 面经
相关话题的讨论汇总
话题: string话题: std话题: word话题: input话题: words