热搜：编程 Python Microsoft 编程语言 C++

匹配正则表达式中的'.','*'

发布时间：2024-03-20 23:14:32 来源：互联网

.

package 牛客网剑指offer题库;public class 正则表达式匹配 {public static void main(String[] args

package 牛客网剑指offer题库;


public class 正则表达式匹配 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        正则表达式匹配 test=new 正则表达式匹配();
        System.out.println(test.match("".toCharArray(),".".toCharArray()));
    }
    
    public boolean match(char[] str, char[] pattern){
            if(str.length==0&&pattern.length==0)return true;
            else return match1(str,pattern,0,0);
    }

    /**
     * si,pi表示当前函数要匹配的字符和对应的正则字符
     * 首先，如果当前字符和正则字符同时走完，则返回true
     * 如果正则字符走完而匹配字符未走完，返回false
     * 如果正在字符未走完，匹配字符已走完，由于'*'的存在,继续匹配，比如ab,abc*
     * 匹配时分为下一个正则字符是*和不是*
     * 如果下一个正则字符存在且是*,那么如果当前字符存在且匹配，则可以选择不匹配当前字符和匹配当前字符，并用当前正则字符匹配下一个字符
     *                         如果当前字符不存在或不匹配，则选择不匹配当前字符
     * 如果下一个不是*，那么如果当前字符存在且匹配，则继续匹配，否则返回false
     * @param str
     * @param pattern
     * @param si
     * @param pi
     * @return
     */
    private boolean match1(char[] str, char[] pattern, int si, int pi) {
        // TODO Auto-generated method stub
        if(si>=str.length&&pi>=pattern.length) return true;
        if(pi>=pattern.length&&si<str.length) return false;
        if((pi+1)<pattern.length&&
                pattern[pi+1]=='*') {
            //如果当前字符匹配，尝试匹配完成或继续匹配
            if(si<str.length&&
                    (pattern[pi]=='.'||pattern[pi]==str[si])) {
                return match1(str, pattern, si, pi+2)
                        ||match1(str,pattern,si+1,pi);
            }else
                return match1(str, pattern, si, pi+2);
        }else {
            if(si<str.length&&
                    (pattern[pi]=='.'||pattern[pi]==str[si]))
                return match1(str, pattern,si+1,pi+1);
            else
                return false;
        }
    }
}