Google onsite

momoly27 发表于 2017-1-13 03:59
楼主可以说说第二题什么思路嘛？

第二题最优解我没想出来。 走之前面试官提示了 wild card  我到现在也没想出来。 这个题coner case 就是如果第一个字母就是typo的情况

五轮一共多少题目？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

laiguojiuhao 发表于 2017-1-16 05:48
楼主请问你是怎么做的？可以像word ladder那样对这个给的词每个位置替换一下吗，这样复杂度就是O(26*len( ...

你这样应该是O(26^len)把。。。 这题感觉用Trie做，然后DFS会好一些？

小A要当码农 发表于 2017-1-16 06:00
你这样应该是O(26^len)把。。。 这题感觉用Trie做，然后DFS会好一些？

Are you sure?

laiguojiuhao 发表于 2017-1-16 06:17
Are you sure?

你的意思是一个个字母穷举26种替换么？ 那复杂度不就是26 ^ len?

小A要当码农 发表于 2017-1-16 06:30
你的意思是一个个字母穷举26种替换么？ 那复杂度不就是26 ^ len?

但是只有一个字母错了，所以只需要替换一个

laiguojiuhao 发表于 2017-1-16 06:34
但是只有一个字母错了，所以只需要替换一个

但是并不知道是哪个字母错了呀。。

小A要当码农 发表于 2017-1-16 06:47
但是并不知道是哪个字母错了呀。。

1. 
   
2. def func():
   
3.     word = 'applr'
   
4.     for idx in range(len(word)):
   
5.         for ch in 'abcdefghijklmnopqrstuvwxyz':
   
6.             new_word = word[:idx] + ch + word[idx+1:]
   
7.             if new_word in dictionary:
   
8.                 return True
   
9.     return False
   

复制代码

所以替换每一个一次啊。我知道你啥意思，你是替换了第一个的基础上继续替换第二个，但是实际上替换第二个你要保持第一个不变。。。应该没错吧你看看，难道是我没睡醒吗。。。