leetcode 212 测试case问题

以下是三个月前通过leetcode OJ 的代码：

//my 10/17/2018
struct TrieNode {
    vector<TrieNode*> child = vector<TrieNode*>(26, nullptr);//you cannot initialize here: (26, nullptr);****************
    string name="";
};
struct Trie {
    TrieNode* root=new TrieNode();//***************
    void insert(string a) {
        auto p = root;
        for (auto aa : a) {
            if (p->child[aa - 'a'] == nullptr)
                p->child[aa - 'a'] = new TrieNode();
            p = p->child[aa - 'a'];
        }
        p->name = a;
    }
};

void helper(vector<vector<char>>&board, vector<vector<bool>>visit, TrieNode* p, int i, int j, vector<string> &ans) {
    if (!p->name.empty()) {
        ans.push_back(p->name);
        p->name.clear();
        return;
    }
    int m = board.size(), n = board[0].size();
    if (i >= 0 && j >= 0 && i<m&&j<n && !visit[i][j] && p->child[board[i][j] - 'a']) {
        visit[i][j] = true;
        helper(board, visit, p->child[board[i][j] - 'a'], i + 1, j, ans);
        helper(board, visit, p->child[board[i][j] - 'a'], i - 1, j, ans);
        helper(board, visit, p->child[board[i][j] - 'a'], i, j + 1, ans);
        helper(board, visit, p->child[board[i][j] - 'a'], i, j - 1, ans);

        visit[i][j] = false;
    }
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    vector<string> ans;
    if (words.empty() || board.empty() || board[0].empty())
        return {  };
    Trie dic;
    for (auto a : words)
        dic.insert(a);

    int m = board.size(), n = board[0].size();
    TrieNode* p = dic.root;
    vector<vector<bool>> visit(m, vector<bool>(n, false));
    for (int i = 0; i<m; i++) {
        for (int j = 0; j<n; j++)
            helper(board, visit, p, i, j, ans);
    }
    return ans;
}

• 主要思想：dfs 的思想。

1. 首先遍历全部dic中的单词，将单词添加到Trie中。
2. 从左上角遍历board 每一个元素都有可能成为起点，所以两层循环中间的关键代码就是直接进入DFS
3. helper() 这里面就不用过多解释，简单的遍历四个方向 接下来的重点就是为什么test case 在leetcode中是不充足的：

以上的代码是可以通过leetcode并且有时间分析的。可是在lintcode132里面就不可以，错误的例子是：
["abcde","tsrqf","mnopg","lkjih"]
["abcdefghijklmnopqrst","abcd","kj","op"] ---字典
我们注意到abcd abcde...是在前半部分完全重复。在helper中如果遇到name!=""就返回答案，后面“abcdef...”将没有机会遍历到。
所以正确的代码是 将return 注释掉~~

//i132
class Solution {
public:
    struct TrieNode {
        vector<TrieNode*> child = vector<TrieNode*>(26, nullptr);
        string name = "";
    };
    struct Trie {
        TrieNode* root = new TrieNode();

        void insert(string a) {
            TrieNode* temp = root;
            for (auto aa : a) {
                if (temp->child[aa - 'a'] == nullptr) {
                    temp->child[aa - 'a'] = new TrieNode();
                }
                temp = temp->child[aa - 'a'];
            }
            temp->name = a;
        }
    };
    void helper(vector<vector<char>>& board, int i, int j, TrieNode* trie, vector<string>& ans, vector<vector<bool>>& visited) {
        if (trie->name != "") {
            ans.push_back(trie->name);
            trie->name.clear();
            //return;//******new change for lintcode
        }
        int m = board.size(), n = board[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || trie->child[board[i][j] - 'a'] == nullptr || visited[i][j] == true)
            return;
        visited[i][j] = true;
        helper(board, i + 1, j, trie->child[board[i][j] - 'a'], ans, visited);
        helper(board, i - 1, j, trie->child[board[i][j] - 'a'], ans, visited);
        helper(board, i, j + 1, trie->child[board[i][j] - 'a'], ans, visited);
        helper(board, i, j - 1, trie->child[board[i][j] - 'a'], ans, visited);
        visited[i][j] = false;
    }
    vector<string> wordSearchII(vector<vector<char>>& board, vector<string>& words) {
        if (board.empty() || board[0].empty())
            return {};
        Trie dic;
        for (auto aa : words) {
            dic.insert(aa);
        }
        int m = board.size(), n = board[0].size();
        vector<string> ans;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                helper(board, i, j, dic.root, ans, visited);
            }
        }
        return ans;
    }



int main()
{
    vector<string> words = { "abcdefghijklmnopqrst","lkjihmonpgfqrstabcde","mo","mn","mnopg","kj","op" };//,"abcde"
    vector<vector<char>> board = { {'a','b','c','d','e'},
                                    {'t','s','r','q','f'},
                                    {'m','n','o','p','g' },
                                    {'l', 'k', 'j', 'i','h'} };
    Solution ans;
    vector<string> aa = ans.wordSearchII(board, words);

    getchar();
    return 0;
}
};