【LeetCode-面試算法經典-Java實作】【010-Regular Expresssion Matching（正規表達式比對）】

【010-Regular Expresssion Matching（正規表達式比對）】

【LeetCode-面試算法經典-Java實作】【所有題目目錄索引】

原題

　　Implement regular expression matching with support for ‘.’ and ‘*’. ‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element.The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p)

　　Some examples:

　　isMatch(“aa”,”a”) → false

　　isMatch(“aa”,”aa”) → true

　　isMatch(“aaa”,”aa”) → false

　　isMatch(“aa”, “a*”) → true

　　isMatch(“aa”, “.*”) → true

　　isMatch(“ab”, “.*”) → true

　　isMatch(“aab”, “c*a*b”) → true

題目大意

　　實作一個正規表達式比對算法，.比對任意一個字元，*比對0個或者多個前導字元

解題思路

　　使用标記比對算法法，從後向前進行比對。

代碼實作

import java.util.Arrays;

public class Solution {
    /**
     * 010-Regular Expresssion Matching（正規表達式比對）
     * 
     * @param s 比對串
     * @param p 模式串
     * @return 比對結果，true比對，false不比對
     */
    public boolean isMatch(String s, String p) {
        // 标記數數組
        boolean[] match = new boolean[s.length() + ];
        // 初始化
        Arrays.fill(match, false);
        // 假定最後的結果是比對的
        match[s.length()] = true;

        // 對模式串從後向前進行處理
        for (int i = p.length() - ; i >= ; i--) {

            // 如果目前是*
            if (p.charAt(i) == '*') {

                // 比對串從最後一個開始處理
                for (int j = s.length() - ; j >= ; j--)  {
                    match[j] = match[j] || match[j + ] && (p.charAt(i - ) == '.' || s.charAt(j) == p.charAt(i - ));
                }
                i--;
            }
            // 如果不是*
            else {
                for (int j = ; j < s.length(); j++) {
                    match[j] = match[j + ] && (p.charAt(i) == '.' || p.charAt(i) == s.charAt(j));
                }

                match[s.length()] = false;
            }
        }
        return match[];
    }
}
           

評測結果

　　點選圖檔，滑鼠不釋放，拖動一段位置，釋放後在新的視窗中檢視完整圖檔。

特别說明

歡迎轉載，轉載請注明出處【http://blog.csdn.net/derrantcm/article/details/46951847】