LeetCode 中的输出和我的本地输出结果不一致

题目是 LeetCode 211: https://leetcode.com/problems/add-and-search-word-data-structure-design/description/
我提交代码之后，发现是第一个 test case 错误（下图中红色下划线处），正确答案为 true，而我输出了 false，如下图：

但是当我在本地 Visual Studio 里调试的时候，发现对于这个 test case 的输出却是 true


本人百思不得其解。。。特来求助
我的代码如下：

1. #include <string>
   
2. #include <unordered_map>
   
3. using namespace std;
   
4. 
   
5. struct TrieNode {
   
6.         unordered_map<char, TrieNode*> next;
   
7.         bool is_word;
   
8.         TrieNode() : is_word(false) {}
   
9. };
   
10. 
    
11. class WordDictionary {
    
12. public:
    
13.         /** Initialize your data structure here. */
    
14.         WordDictionary() {
    
15.                 root = new TrieNode();
    
16.         }
    
17. 
    
18.         /** Adds a word into the data structure. */
    
19.         void addWord(string word) {
    
20.                 TrieNode* curr = root;
    
21.                 for (char c : word) {
    
22.                         if (curr->next.find(c) == curr->next.end()) {
    
23.                                 curr->next[c] = new TrieNode();
    
24.                         }
    
25.                         curr = curr->next[c];
    
26.                 }
    
27.                 curr->is_word = true;
    
28.         }
    
29. 
    
30.         /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    
31.         bool search(string word) {
    
32.                 TrieNode* node = dfs(word, 0, root);
    
33.                 return node != NULL && node->is_word;
    
34.         }
    
35. private:
    
36.         TrieNode * root;
    
37. 
    
38.         TrieNode * dfs(string& target, int index, TrieNode* curr) {
    
39.                 if (index == target.size()) {
    
40.                         return curr;
    
41.                 }
    
42.                 char c = target[index];
    
43.                 if (c == '.') {
    
44.                         for (auto it = curr->next.begin(); it != curr->next.end(); ++it) {
    
45.                                 TrieNode* found = dfs(target, index + 1, it->second);
    
46.                                 if (found != NULL) {
    
47.                                         return found;
    
48.                                 }
    
49.                         }
    
50.                         return NULL;
    
51.                 }
    
52.                 auto it = curr->next.find(c);
    
53.                 return it == curr->next.end() ? NULL : dfs(target, index + 1, it->second);
    
54.         }
    
55. };
    
56. 
    
57. int main() {
    
58.         WordDictionary wd;
    
59.         bool r;
    
60. 
    
61.         wd.addWord("ran");
    
62.         wd.addWord("rune");
    
63.         wd.addWord("runner");
    
64.         wd.addWord("runs");
    
65.         wd.addWord("add");
    
66.         wd.addWord("adds");
    
67.         wd.addWord("adder");
    
68.         wd.addWord("addee");
    
69. 
    
70.         r = wd.search("r.n");                // true
    
71.         r = wd.search("ru.n.e");        // false
    
72.         r = wd.search("add");                // true
    
73.         r = wd.search("add.");                // true
    
74.         r = wd.search("adde.");                // true
    
75.         r = wd.search(".an.");                // false
    
76.         r = wd.search("...s");                // true
    
77.         r = wd.search("....e.");        // true
    
78.         r = wd.search(".......");        // false
    
79.         r = wd.search("..n.r");                // false
    
80. 
    
81.         return 0;
    
82. }

复制代码

这个是因为你在遇到'.'的时候应该遍历那一层的所有node，但是你只选了一个，因为你用了unordered_map，所以实际上是随机选的，这就是为什么你在本地和leetcode上结果不一样。

在第46行的if里面加一个条件

1. && found->is_word

复制代码

补充内容 (2018-6-11 22:00):
说是随机不太好，应该说是顺序不定

给你举个例子

["WordDictionary","addWord","addWord","search"]
[[],["ran"],["rune"], ["r.."]]

这个test case你代码过不了.

我不是特别懂c++, 我猜大概是因为你dfs吧.. 似乎是找没找到都返回了?

肥宅快乐水 发表于 2018-6-10 20:28
给你举个例子

["WordDictionary","addWord","addWord","search"]

谢谢，但是你给的这个例子，我的代码在IDE里是可以输出正确的结果的（true），不知道你为什么说过不了呢？

肥宅快乐水 发表于 2018-6-10 20:28
给你举个例子

["WordDictionary","addWord","addWord","search"]

没找到的话，dfs返回NULL，然后search就会返回false

fluu 发表于 2018-6-11 10:54
谢谢，但是你给的这个例子，我的代码在IDE里是可以输出正确的结果的（true），不知道你为什么说过不了呢 ...

哦我这个是leetcode上过不了的, 你试试.

我没有ide, 没办法在这边帮你看.

肥宅快乐水 发表于 2018-6-10 21:53
哦我这个是leetcode上过不了的, 你试试.

我没有ide, 没办法在这边帮你看.

好吧。。。我问的就是LC和本地IDE显示结果不一致

fluu 发表于 2018-6-11 12:39
好吧。。。我问的就是LC和本地IDE显示结果不一致

我猜了一下大概有几个原因吧..

1. 你的unordered map的visit顺序是unordered, 也许你电脑上的刚好就先走ra, 但是lc那边先走ru.

2. 你回复的逻辑其实我不是特别懂, 可以解释一下嘛..? 你的dfs走到底没有找到的时候, 会回溯回来然后检查到下一个.位置上的character嘛?

不能只是“百思”不得其解.. 要debug

第一步是切割输入从而在尽量简化的情况下重现错误，这个楼上已经指出来一个很好的case：

1. ["WordDictionary","addWord","addWord","search"]
   
2. [[],["ran"],["rune"], ["r.."]]

复制代码

然后在一些关键点上添加输出，看看是不是与期望值一致。

既然search返回的值不正确，那么先从这里入手，添加一点输出：

1.     bool search(string word) {
   
2.         TrieNode* node = dfs(word, 0, root);
   
3.         std::cout << "node = " << node << "\n";
   
4.         if (node != NULL) {
   
5.           std::cout << "is word = " << node->is_word << "\n";
   
6.         }
   
7.         return node != NULL && node->is_word;
   
8.     }

复制代码

在LeetCode上Run Code执行后，你会发现输出显示node不为NULL，但是is word是false

这里其实应该可以猜出来是什么问题了，就是上面楼层所提到的返回了一个非word节点（例如rune的前缀"run"匹配"r.."，但是run并不是word节点）

当然如果没有想到这一点的话，可以进一步追索为什么会返回一个is_word = false的点，那就是打印递归过程：

1.     TrieNode * dfs(string& target, int index, TrieNode* curr) {
   
2.         if (index == target.size()) {
   
3.             std::cout << "Returning!\n";
   
4.             return curr;
   
5.         }
   
6.         char c = target[index];
   
7.         if (c == '.') {
   
8.             for (auto it = curr->next.begin(); it != curr->next.end(); ++it) {
   
9.                 std::cout << std::string(index, ' ') << it->first << "\n";
   
10.                 TrieNode* found = dfs(target, index + 1, it->second);
    
11.                 if (found != NULL) {
    
12.                     return found;
    
13.                 }
    
14.             }
    
15.             return NULL;
    
16.         }
    
17.         auto it = curr->next.find(c);
    
18.         std::cout << std::string(index, ' ') << it->first << "\n";
    
19.         return it == curr->next.end() ? NULL : dfs(target, index + 1, it->second);
    
20.     }
    

复制代码

Run Code执行后你会发现打印出来的是按r->u->n的顺序走并且返回的，这时候整个程序的执行过程以及问题所在应该就很直观了。

感谢楼上诸位高手