Noob
0%

字符串匹配（待完成）

发表于 更新于 分类于 ，

字符串匹配（简版）

https://leetcode.com/problems/wildcard-matching/
“?”代表一个任意的字符，”*“ 代表0个或多个字符

有限状态机（DFA）

记录下不匹配的位置，然后依次回溯

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
public boolean isMatch(String s, String p) {
    if(s == null || p == null) return false;
    
    int i = 0, j = 0;
    int ti = -1, tj = -1;
    while(i < s.length()) {
        if(i < s.length() && j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
            ++i;
            ++j;
        }else if(j < p.length() && p.charAt(j) == '*') {
            while(j < p.length() && p.charAt(j) == '*') ++j;
            if(j == p.length()) return true;
            ti = i;
            tj = j;
        }else if(tj != -1 && (j == p.length() || p.charAt(j) != s.charAt(i))) {
            i = ++ti;
            j = tj;
        } else
            return false;
    }
    while(j < p.length()) {
        if(p.charAt(j) != '*')
            return false;
        else
            ++j;
    }
    return true;
}

二维DP

用一个二维数组dp[p.length() + 1][s.length() + 1]记录字符串s和模式串p的匹配情况，其中dp[i][j]表示s[0j]是否与p[0i]匹配，如果匹配dp[i][j]=true，否则dp[i][j]=false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isMatch(String s, String p) {
    if(s == null || p == null) return false;
    
    boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
    dp[0][0] = true;
    for(int i = 0; i < p.length(); ++i) {
        //如果p[i]=='*'，dp[i+1][0]=dp[i][0]，因为此时的转移方程dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j]需要用到dp[i + 1][j]的值，而dp[i + 1][0]初始应该是dp[i][0]
        if(p.charAt(i) == '*') dp[i + 1][0] = dp[i][0];
        for(int j = 0; j < s.length(); ++j) {
            if(p.charAt(i) == '*')
                //设计和分析转移方程时有一个技巧：不看固定不变的量，只把注意力放在变化的量上。例如dp[i + 1][j + 1]与dp[i][j + 1]只看i -> i + 1，即p从第i个字符状态转移到第i+ 1个字符状态的过程（忽略相同的s的第j+1个字符位置）。
                dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j] ;
            else
                dp[i + 1][j + 1] = dp[i][j] && (p.charAt(i) == '?' || s.charAt(j) == p.charAt(i));
        }
    }
    return dp[p.length()][s.length()];
}

一维DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isMatch(String s, String p) {
    if(s == null || p == null) return false;
    
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for(int i = 0; i < p.length(); ++i) {
        if(p.charAt(i) == '*') {
            for(int j = 0; j < s.length(); ++j)
                dp[j + 1] = dp[j] || dp[j + 1];
        } else {
            for(int j = s.length() - 1; j >= 0; --j)
                dp[j + 1] = dp[j] && (p.charAt(i) == '?' || p.charAt(i) == s.charAt(j));
            dp[0] = false;
        }
    }
    return dp[s.length()];
}

字符串匹配（繁版）

https://leetcode.com/problems/regular-expression-matching/
“.”代表一个任意的字符，”*“ 代表它前面的 0个或多个字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isMatch(String s, String p) {
    if(s == null || p == null) return false;
    return isMatch(s, p, 0, 0);
}

private boolean isMatch(String s, String p, int si, int pi) {
    if(si == s.length()) {
        while(pi + 1 < p.length() && p.charAt(pi + 1) == '*') pi += 2;
        return pi == p.length();
    }
    
    boolean result = false;
    if(pi < p.length() && (p.charAt(pi) == '.' || p.charAt(pi) == s.charAt(si)))
        result = result || isMatch(s, p, si + 1, pi + 1);
    if(pi + 1 < p.length() && p.charAt(pi + 1) == '*') {
        result = result || isMatch(s, p, si, pi + 2);
        if(p.charAt(pi) == '.' || p.charAt(pi) == s.charAt(si))
            result = result || isMatch(s, p, si + 1, pi);
    }
    return result;
}

http://bangbingsyb.blogspot.tw/2014/11/leetcode-regular-expression-matching.html
http://blog.csdn.net/linhuanmars/article/details/21145563