google电面

二院老同志 发表于 2018-10-17 10:01
keyboard上的字符应该是不会重复的吧，那是不是就是用个map存一下每个char的坐标，然后遍历string，相邻两 ...

应该是这么做，不过貌似不知道有没有重复的char，如果有的话可能还要用list管理每一个char的成员。然后像找字母一样做dfs。基本思路都是dfs，只不过这道题的范围从上下左右扩大到了maxstep覆盖的区域。

二院老同志 发表于 2018-10-17 10:01
keyboard上的字符应该是不会重复的吧，那是不是就是用个map存一下每个char的坐标，然后遍历string，相邻两 ...

是不重复的，你这个方法太棒了！但是我面试的时候就是用dfs做的。

建图，然后BFS/DFS

感谢分享

有后续了么

Lego0o0 发表于 2018-10-18 03:43
是不重复的，你这个方法太棒了！但是我面试的时候就是用dfs做的。

请问楼主，DFS可以吗？应该用BFS吧？

二院老同志 发表于 2018-10-17 10:01
keyboard上的字符应该是不会重复的吧，那是不是就是用个map存一下每个char的坐标，然后遍历string，相邻两 ...

这个方法好赞。另外即使有重复，也可以用类似的方法，map里存每个character和其对应坐标的list。然后用DFS， 如果某一个character存在多个不同在距离内的position，recursively check每一个position, 如果采用这个position可以最终成功打印出单词，则return true，如果所有position都fail，则返回false。