google onsite 2/29

panlong222 发表于 2016-3-2 07:02
“两个substring只有一个字母不同” 指的是 一定有一个字母不同 还是 最多有一个字母不同？

abcde和abdde这样，有且只有一个字母不同

hzyslddm 发表于 2016-3-2 07:05
abcde和abdde这样，有且只有一个字母不同

就是说长度也一致？  然后每个index的character都一样，除了一个不一样，对吧？

panlong222 发表于 2016-3-2 07:21
就是说长度也一致？  然后每个index的character都一样，除了一个不一样，对吧？

是的，字数字数

第四题 我想法是N^3

列出所有substring (n^2)
    对于每一个substring substr, 把substr的每个character改为a-z（就像word ladder一样）看hashset里面有没有，有的话就是一个pair (n)
    把这个substr放入hashset

所以最后是26*n^3

csgtc 发表于 2016-3-2 07:47
第四题 我想法是N^3

列出所有substring (n^2)

character是任意的，不是仅仅a-z
不过LZ的做法也没有用到dp的好处，只是没时间讨论优化了

hzyslddm 发表于 2016-3-1 19:11
character是任意的，不是仅仅a-z
不过LZ的做法也没有用到dp的好处，只是没时间讨论优化了

如果是任意character也是256*n^3，比n^4好啊。。

csgtc 发表于 2016-3-2 15:14
如果是任意character也是256*n^3，比n^4好啊。。

只是纠正一下不能做那个字符都是字母的assumption,不是说你的算法不行。。另外，用hashset可能会漏算，比如aab这样的字符串，"a"和"b"这样的pair有两组,感觉要改用hashmap

hzyslddm 发表于 2016-3-3 03:59
只是纠正一下不能做那个字符都是字母的assumption,不是说你的算法不行。。另外，用hashset可能会漏算，比 ...

不知道有没有离解错题目意思? 第一步先枚举所有的substrings o(n^3) 第二步根据长度分类每一个长度里面分别做edit distance 的check o(n^3) 这样可行吗? LZ

say543 发表于 2016-3-4 15:50
不知道有没有离解错题目意思? 第一步先枚举所有的substrings o(n^3) 第二步根据长度分类每一个长度里面分 ...

恩 我的思路和你差不多， 也是O(n^3), 这题有n2的解法么？

say543 发表于 2016-3-4 15:50
不知道有没有离解错题目意思? 第一步先枚举所有的substrings o(n^3) 第二步根据长度分类每一个长度里面分 ...

恩 我的思路和你差不多， 也是O(n^3), 这题有n2的解法么？