212 单词搜索Ⅱ

发表于 | 分类于 |

212 单词搜索II

难度：困难

平台：leetcode

Description

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例: 

1
2
3
4
5
6
7
8
9
10
11
输入:
words = ["oath","pea","eat","rain"]
board =
[
 ['o','a','a','n'],
 ['e','t','a','e'],
 ['i','h','k','r'],
 ['i','f','l','v']
]

输出:["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。
原题链接

MySolution

这类字符串多模式匹配题目，第一反映是前缀树，关于前缀树在这里就不过多介绍了。此题基本思路是，将words字符串数组构造成前缀树，然后对board的每个字符用前缀树去匹配。当时做这道题花了一定的时间主要是因为用前缀树去匹配时涉及状态回溯，要在每次失败或者结束后回到上一个状态，并且不可遗漏，一开始写题时没有考虑周到。接下来上拆解代码。 ### 结点定义 

1
2
3
4
5
6
7
8
9
10
11
class node{
    //节点结构
    ArrayList<node> nodes=new ArrayList<node>();
    boolean isEnd;
    char value;
    public node(boolean isEnd, char value) {
        super();
        this.isEnd = isEnd;
        this.value = value;
    }
}

构造前缀树

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
public void init(String[] words) {
    //构造前缀树
    for(String s:words) {
        Solution.node cur=root;
        char[] a=s.toCharArray();
        for (int i = 0; i < a.length; i++) {
            boolean flag=false;
            for(Solution.node n:cur.nodes) {
                if(n.value==a[i]) {
                    flag=true;
                    if(i==a.length-1) {
                        n.isEnd=true;
                        break;
                    }else {
                        cur=n;
                        break;
                    }
                }
            }
            if(!flag) {
                if(i!=a.length-1) {
                    cur.nodes.add(new Solution.node(false, a[i]));
                    cur=cur.nodes.get(cur.nodes.size()-1);
                }else {
                    cur.nodes.add(new Solution.node(true, a[i]));
                    cur=cur.nodes.get(cur.nodes.size()-1);
                }
            }
        }
    }
}

前缀树匹配

前缀树匹配时采用递归+回溯的思想 

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
public void find(int i,int j,node cur,int[][] visited,String rString) {
    if(i<m && i>=0 && j>=0 &&j<n && visited[i][j]!=1) //判断边界
    {
        visited[i][j]=1;
        for(node n:cur.nodes) //遍历当前节点子结点
        {
            if(boards[i][j]!=n.value) //子节点未找到相同字母
                continue;
            else //子节点找到相同字母
            {
                rString+=boards[i][j];//添加到结果String
                if (n.isEnd) //添加到结果String集
                    result.add(rString);
                cur=n;//子节点变成当前结点
                if(n.nodes.isEmpty()) {
                    visited[i][j]=0;
                    return;
                }
                for(int k=0;k<4;k++) {
                    find(i+x[k], j+y[k], cur, visited, rString);
                }
                //查询四周
                visited[i][j]=0;
            }
        }
        //子节点内无相同结点
        visited[i][j]=0;
        return;
    }else {
        return;
    }
}

整体代码

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import java.util.*;

class Solution {
    node root=new node(false, '*');
    char[][] boards;
    Set<String> result=new HashSet<String>();

    int[] x= {0,-1,1,0};//负责向四周移动
    int[] y= {-1,0,0,1};//负责向四周移动

    int m,n;
    public void init(String[] words) {
        //构造前缀树
        for(String s:words) {
            node cur=root;
            char[] a=s.toCharArray();
            for (int i = 0; i < a.length; i++) {
                boolean flag=false;
                for(node n:cur.nodes) {
                    if(n.value==a[i]) {
                        flag=true;
                        if(i==a.length-1) {
                            n.isEnd=true;
                            break;
                        }else {
                            cur=n;
                            break;
                        }
                    }
                }
                if(!flag) {
                    if(i!=a.length-1) {
                        cur.nodes.add(new node(false, a[i]));
                        cur=cur.nodes.get(cur.nodes.size()-1);
                    }else {
                        cur.nodes.add(new node(true, a[i]));
                        cur=cur.nodes.get(cur.nodes.size()-1);
                    }
                }
            }
        }
    }
    public void find(int i,int j,node cur,int[][] visited,String rString) {
        if(i<m && i>=0 && j>=0 &&j<n && visited[i][j]!=1) //判断边界
        {
            visited[i][j]=1;
            for(node n:cur.nodes) //遍历当前节点子结点
            {
                if(boards[i][j]!=n.value) //子节点未找到相同字母
                    continue;
                else //子节点找到相同字母
                {
                    //访问标记
                    rString+=boards[i][j];//添加到结果String
                    if (n.isEnd) //添加到结果String集
                        result.add(rString);
                    cur=n;//子节点变成当前结点
                    if(n.nodes.isEmpty()) {
                        visited[i][j]=0;
                        return;
                    }
                    for(int k=0;k<4;k++) {
                        find(i+x[k], j+y[k], cur, visited, rString);
                    }
                    //查询四周
                    visited[i][j]=0;
                }
            }
            //子节点内无相同结点
            visited[i][j]=0;
            return;
        }else {
            return;
        }

    }
    public List<String> findWords(char[][] board, String[] words) {
        init(words);
        boards=board;
        m=boards.length;
        n=boards[0].length;
        for (int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                int[][] visited=new int[board.length][board[0].length];
                String rString="";
                find(i,j,root,visited,rString);
            }
        }
        List<String> ans=new ArrayList<String>();
        for (String string : result) {
            ans.add(string);
        }
        Collections.sort(ans);
        return ans;
    }
    class node{
        //节点结构
        ArrayList<node> nodes=new ArrayList<node>();
        boolean isEnd;
        char value;
        public node(boolean isEnd, char value) {
            super();
            this.isEnd = isEnd;
            this.value = value;
        }
    }
}

有的没的

这一分类主要记录自己做过的一些还比较有意义的题目的解题历程以及一些个人思考，菜鸡起步而已，希望自己能坚持下去，然后能有所进步吧。