【华为校招】【校招】【Java】字符串匹配（DP）

■ 题目描述
【字符串匹配】
给你一个字符串数组（每个字符串均由小写字母组成）和一个字符规律（由小写字母和.和组成），识别数组中哪些字符串可以匹配到字符规律上。
‘.’ 匹配任意单个字符，’’ 匹配零个或多个前面的那一个元素，所谓匹配，是要涵盖整个字符串的，而不是部分字符串。
输入描述
第一行为空格分割的多个字符串，1<单个字符串长度<100，0，1<字符串个数<100
第二行为字符规律，1<字符串个数<100
第二行为字符规律，1<=字符规律长度<=50
不需要考虑异常场景。
输出描述
匹配的字符串在数组中的下标（从0开始），多个匹配时下标升序并用,分割，若均不匹配输出-1
示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
ab aab

输出
0,1
示例2 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
ab abc bsd

输出
0,1,2
示例3 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
avd adb sss as
adb
输出
1

public class StringMatch {

    public boolean isMatch(String s,String p){
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        int m = cs.length, n = cp.length;
        boolean[][] dp = new boolean[m+1][n+1];
        // 初始化
        dp[0][0] = true;
        // p为空，s不为空，必为false(boolean数组默认值为false，无需处理)

        // s为空，p不为空，由于*可以匹配0个字符，所以有可能为true
        for (int i=1;i<=n;i++){
            if (cp[i-1]=='*'){
                dp[0][i] = true;
            }
        }

        // 填格子
        for (int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                // 文本串和模式串末位字符能匹配上
                if (cs[i-1]==cp[j-1]||cp[j-1]=='.'){
                    dp[i][j] = dp[i-1][j-1];
                }else if (cp[j-1]=='*'){
                    // 模式串末位是*
                    // 模式串*的前一个字符能够跟文本串的末位匹配上
                    if (cs[i-1]==cp[j-2]||cp[j-2]=='.'){
                        dp[i][j]=dp[i][j-2] // *匹配0次的情况
                                ||dp[i-1][j];// *匹配1次或多次的情况
                    }else {
                        dp[i][j] = dp[i][j-2];
                    }
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        String p = sc.nextLine();
        StringMatch stringMatch = new StringMatch();
        List<Integer> ans = new ArrayList<Integer>();
        for (int i=0;i<s.length;i++){
            if (stringMatch.isMatch(s[i],p)){
                ans.add(i);
            };
        }
        if (ans.size()==0){
            System.out.println(-1);
        }else {
            StringBuilder sb = new StringBuilder();
            for (int i=0;i<ans.size();i++){
                sb.append(ans.get(i));
                if (i<ans.size()-1){
                    sb.append(",");
                }
            }
            System.out.println(new String(sb));
        }
    }
}
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