習(xí)慣github pages風(fēng)格的請(qǐng)看我的另一篇博客

題目19：正則表達(dá)式匹配

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來匹配包括.和*的正則表達(dá)式。模式中的字符.表示任意一個(gè)字符，而*表示它前面的字符可以出現(xiàn)任意次（包含0次）。 匹配是指字符串的所有字符匹配整個(gè)模式。

舉例說明

例如，字符串aaa與模式a.a和ab * ac * a匹配，但與aa.a和ab * a均不匹配

思路

遞歸實(shí)現(xiàn)

模式字符串pattern和待匹配字符串Str。匹配是指Str的所有字符匹配整個(gè)pattern。

• 每次從Str里拿出一個(gè)字符和pattern中的字符去匹配，主要的核心
  • 1.下一個(gè)是不是*
  • 2.str是否結(jié)束
  • （3.當(dāng)前字符是否匹配）

對(duì)每一個(gè)字符

• 1. 一對(duì)多匹配：如果模式匹配字符的下一個(gè)字符是*
  • 1.1 str已經(jīng)結(jié)束：match(s, p+2)
  • 1.2 str沒有結(jié)束：
    • 1.2.1如果pttern當(dāng)前字符和str的當(dāng)前字符匹配，：有以下三種可能情況
      1）pttern當(dāng)前字符能匹配 str 中的 0 個(gè)字符：match(s, p+2)
      2）pttern當(dāng)前字符能匹配 str 中的 1 個(gè)字符：match(s+1, p+2)
      3）pttern當(dāng)前字符能匹配 str 中的 多 個(gè)字符：match(s+1, p)
    • 1.2.2 如果pttern當(dāng)前字符和和str的當(dāng)前字符不匹配
      pttern當(dāng)前字符能匹配 str 中的 0 個(gè)字符：match(s, p+2)
• 2. 一對(duì)一匹配 ：如果模式匹配字符的下一個(gè)字符不是*
  • 2.1 str已經(jīng)結(jié)束：return false;
  • 2.2 str沒有結(jié)束：
    • 2.1.1 匹配：
      如果pattern中的字符ch是.或Str中的字符是ch，則對(duì)應(yīng)位置匹配，在Str和pattern上都向后移動(dòng)一個(gè)字符，也就是match(s+1, p+1)
    • 2.1.2 不匹配：return false;

代碼實(shí)現(xiàn)

public class _19 {
    public static boolean match(String str, String pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        return matchCore(str, 0, pattern, 0);
    }

    private static boolean matchCore(String str, int s, String pattern, int p) {
        // str和pattern都到達(dá)尾，說明成功匹配
        if (s >= str.length() && p >= pattern.length()) {
            return true;
        }
        // 只有pattern到達(dá)結(jié)尾，說明匹配失敗
        if (s != str.length() && p >= pattern.length()) {
            return false;
        }

        //pattern未結(jié)束，str有可能結(jié)束有可能未結(jié)束
        // 1  --------------------------------------------
        if (p + 1 < pattern.length() && pattern.charAt(p + 1) == '*') {
            if (s >= str.length()) {// 1.1  --------------------------------------------
                return matchCore(str, s, pattern, p + 2);
            }
            // 1.2  --------------------------------------------
            else {//1.2.1----------------------------------------
                if (pattern.charAt(p) == str.charAt(s) || pattern.charAt(p) == '.') {
                    return
                            // 當(dāng)前pattern匹配當(dāng)前str 0個(gè)字符，如aa*a與aa
                                matchCore(str, s, pattern, p + 2)
                            // 當(dāng)前pattern匹配當(dāng)前str 1個(gè)字符，如ab*a與aba
                            ||  matchCore(str, s + 1, pattern, p + 2)
                            //當(dāng)前pattern匹配當(dāng)前str 多個(gè)字符，如ab*a與aaba
                            ||  matchCore(str, s + 1, pattern, p);
                } else {//1.2.2 如a*與b-----------------------------
                    return matchCore(str, s, pattern, p + 2);
                }
            }
        }
        //2--------------------------------------
        if (s >= str.length() ) {//2.1------------------------------
            return false;
        }
        else {// 2.2----------------------------------
            if (str.charAt(s) == pattern.charAt(p) || pattern.charAt(p) == '.') {
                return matchCore(str, s + 1, pattern, p + 1);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(match("aaa", "ab*ac*a"));//true
        System.out.println(match("aaba", "ab*a*c*a"));//false
        System.out.println(match("bbbba", ".*a*a"));//true
        System.out.println(match("bcbbabab", ".*a*a"));//false
    }
}

輸出

image

相關(guān)學(xué)習(xí)

正則表達(dá)式手冊(cè)