Google intern 电面

sw304 发表于 2019-1-10 12:30
请问楼主第一题怎么答的呀

eat an elephant one bit at a time，密码学中的破解方法 ，可以百度一下

论坛匿名用户 发表于 2019-1-10 23:35
A: abae
B: eded
麻烦的是这样的字符串，a要变成e，但是一旦变成e，A最后一个字符e就无法单独变成d。这 ...

这里说的找不到备用字符是根据什么来决定？我自己的想法是，当在替换A某个字符成B的target char时候，搜素A中是否存在这个target char,是的话就用个$一类等没出现的字符替换，一直走到最后一个字符，如果能==，就找到，不然就是找不到

我想请问一下第二题： 不知道我是不是没理解题意， 这题不是用一个hash做吗？ scan 字符串A， 存map， key是 A的char， value是B的char， 每个iteration检查A的char是不是已经在map里，并且对应的value是不是冲突，不冲突就继续 冲突就return false。请大神指点

fxctm2311 发表于 2019-1-15 10:06
我想请问一下第二题： 不知道我是不是没理解题意， 这题不是用一个hash做吗？ scan 字符串A， 存map， key ...

不是那个经典题。每次变化会把一个字符串内所有相同的字符A变成B。比如 我想把ABA 变成 CDC 是可以的，因为把A变成C，然后把B 变成 D，但是ABA 变成 CDE 是不能的，因为当我想把第一个A变成C的时候，第一个字符串会变成CBC  ， 无论怎么变都变不成CDE。总之 相同的字符是连接着一起变的

赞啦赞啦，谢谢楼主啦

论坛匿名用户 发表于 2019-1-15 10:42
不是那个经典题。每次变化会把一个字符串内所有相同的字符A变成B。比如 我想把ABA 变成 CDC 是可以的，因 ...

嗯。。所以 ABA 是不能变成CDE的对吧？ 这道题只说是判断 string A 能不能变成B， 只要return true or false就可以了是吧？ 而不是需要实际把string A变成B，不知道我理解的对不对，
所以， 如果我维护一个map（Java）， looping string ， 遇到第一个A， map 保存 A -》C， 表示我要把所以的A换成C。 然后 B -》D， 然后又遇见A ，因为已经在map里， 发现value 为C  但是这次我想要的是A-》E， 所以有冲突，就返回false了。 这个思路不对吗？ 谢谢楼主回复

第二题是LC七二的简化

Husky_wang 发表于 2019-1-10 09:40
第二题是不是二维DP的那个edit distance？

简化过的transform option和简化过的返回值 思路是一样的

fxctm2311 发表于 2019-1-15 15:04
嗯。。所以 ABA 是不能变成CDE的对吧？ 这道题只说是判断 string A 能不能变成B， 只要return true or fa ...

我大概知道你说的是哪个题。在你理解的题目中ABC 可不可以变成 DED？是不是因为发现最后一个C想映射成D的时候，D已经被映射过所以会返回false? 但是在我的题目的变化规则中，是可以return true. 因为变化规则只有一条：每次把字符串中的某一个字符 全部变成 另外一个字符。 所以我只需要吧A变成D， 把B变成E， 然后也把C变成D，这样是可以的

shidaohang 发表于 2019-1-15 15:28
第二题是LC七二的简化

我觉得跟LC72不一样。72是动归题，虽然不知道你的动归方程是什么 但是这题看起来不能用动归解决。因为前面的方案会影响后面的选择。