2015年10月6日星期二

Lintcode: word search ii

Given a matrix of lower alphabets and a dictionary. Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position. 

Have you met this question in a real interview? 
Yes
Example
Given matrix:
doafagaidcan
and dictionary:
{"dog", "dad", "dgdg", "can", "again"}

return {"dog", "dad", "can", "again"}


dog:
doafagaidcan
dad:
doafagaidcan
can:
doafagaidcan
again:
doafagaidcan

Challenge
Using trie to implement your algorithm.


Trie search avoid repetitive search

Reference from some guy's codes, failed to find that web




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
struct TrieNode {
    bool  isEnd;
    TrieNode *children[26];
    
    TrieNode()
    {
        isEnd = false;
        memset(children, 0, sizeof(children));
        // function of memset
        /*   
        for(int i =0; i < 26; i++){
            children[i] = NULL;
        }*/
    }
    
    void Add(string s, int index) {
        if (index == s.length()) {
            isEnd = true;
            return;
        } 
        
        if (children[s[index] - 'a'] == NULL)
            children[s[index] - 'a'] = new TrieNode();
        
        children[s[index]-'a']->Add(s, index+1); 
    }
    
    ~TrieNode() {
        for(int i = 0; i < 26; i++) {
            //it's ok to delete NULL pointer
            delete children[i];
        }
    }
};


class Solution {
public:
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    vector<string> wordSearchII(vector<vector<char> > &board, vector<string> &words) {
        unordered_set<string>  ret;
        TrieNode trie; 
        for(int i = 0; i < words.size(); i++) 
            trie.Add(words[i],0);
        
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
        string temp;
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j< board[0].size(); j++) {
                helper(board, visited, &trie, i, j, temp,  ret); 
        }
        //create vector from set
        return vector<string>(ret.begin(), ret.end());
    }
    
    void helper(vector<vector<char>> &grid, 
            vector<vector<bool>> &visited,
            TrieNode *trie,
            int i,
            int j,
            string tmp,
           unordered_set<string> &ret)
    {

        if (!trie || i < 0 || i >= grid.size() || j < 0 || j >=grid[0].size())
             return;        
        if (!trie->children[grid[i][j]-'a'] || visited[i][j]) return;
        
        
        TrieNode *nextNode = trie->children[grid[i][j]-'a'];
        tmp.push_back(grid[i][j]);
        if (nextNode->isEnd)  ret.insert(tmp); 
        //avoid path return to nodes that already passed
        visited[i][j] = true;
        
        int x[] ={0, 0, -1, 1};
        int y[] ={-1,1, 0, 0};
        for(int k = 0; k < 4; k++) 
            helper(grid, visited, nextNode, i+x[k], j+ y[k], tmp, ret);  
            
        visited[i][j] = false; 
    } 
};
发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)