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

2018-06-10 16:03:36 +08:00
 starvedcat

题目是 LeetCode 211: https://leetcode.com/problems/add-and-search-word-data-structure-design/description/

我提交代码之后,发现是第一个 test case 错误(下图中红色下划线处),正确答案为 true,而我输出了 false,如下图:

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

本人百思不得其解。。。特来求助

我的代码如下:

#include <string>
#include <unordered_map>
using namespace std;

struct TrieNode {
	unordered_map<char, TrieNode*> next;
	bool is_word;
	TrieNode() : is_word(false) {}
};

class WordDictionary {
public:
	/** Initialize your data structure here. */
	WordDictionary() {
		root = new TrieNode();
	}

	/** Adds a word into the data structure. */
	void addWord(string word) {
		TrieNode* curr = root;
		for (char c : word) {
			if (curr->next.find(c) == curr->next.end()) {
				curr->next[c] = new TrieNode();
			}
			curr = curr->next[c];
		}
		curr->is_word = true;
	}

	/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
	bool search(string word) {
		TrieNode* node = dfs(word, 0, root);
		return node != NULL && node->is_word;
	}
private:
	TrieNode * root;

	TrieNode * dfs(string& target, int index, TrieNode* curr) {
		if (index == target.size()) {
			return curr;
		}
		char c = target[index];
		if (c == '.') {
			for (auto it = curr->next.begin(); it != curr->next.end(); ++it) {
				TrieNode* found = dfs(target, index + 1, it->second);
				if (found != NULL) {
					return found;
				}
			}
			return NULL;
		}
		auto it = curr->next.find(c);
		return it == curr->next.end() ? NULL : dfs(target, index + 1, it->second);
	}
};

int main() {
	WordDictionary wd;
	bool r;

	wd.addWord("ran");
	wd.addWord("rune");
	wd.addWord("runner");
	wd.addWord("runs");
	wd.addWord("add");
	wd.addWord("adds");
	wd.addWord("adder");
	wd.addWord("addee");

	r = wd.search("r.n");		// true
	r = wd.search("ru.n.e");	// false
	r = wd.search("add");		// true
	r = wd.search("add.");		// true
	r = wd.search("adde.");		// true
	r = wd.search(".an.");		// false
	r = wd.search("...s");		// true
	r = wd.search("....e.");	// true
	r = wd.search(".......");	// false
	r = wd.search("..n.r");		// false

	return 0;
}
2231 次点击
所在节点    问与答
0 条回复

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/461927

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX