欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基础算法题-正则相关

程序员文章站 2022-03-15 21:08:07
...

题一

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:
boolean isMatch(String s, String 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

不考虑转义等特殊情况的匹配。
正则的常见实现方式有三种:DFA、Backtracking、NFA。
这里简单的匹配,可以用以下两种方式,第一种通过递归的方式,第二种通过动态规划。

递归

首先看递归,这里主要共考虑三种情况。
1. 首字符为’*’,直接判定不合法。例如”*sdf”,”s**df”。
2. 第二个字符不为’*’,此时需要判断第一个字符是否可以匹配匹配串的第一个字符,相等或者’.’。相等则匹配串和模式串都截去首字符,递归处理。
3. 第二个字符为’*’,当模式串和匹配串的首字符匹配,此时需要进行两种处理,第一种认为模式串首字符出现0次,跳过模式串前两个字符,进行再匹配。第二种认为模式串首字符出现了多次,再将匹配串截取,再匹配,直至匹配成功或者失败。当模式串和匹配串首字符不匹配,跳过模式串前两个字符,进行再匹配。

递归解决代码如下:

boolean isMatch(String s, String p) {
    if (p.isEmpty())
        return s.isEmpty();
    if (p.startsWith("*"))
        return false;
    if (p.length() == 1 || p.charAt(1) != '*') {
        if (s.isEmpty() || (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0))) {
            return false;
        } else {
            return isMatch(s.substring(1), p.substring(1));
        }
    }
    while (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {
        if (isMatch(s, p.substring(2))) {//出现0次
            return true;
        }
        s = s.substring(1);
    }
    //出现0次
    return isMatch(s, p.substring(2));
}
动态规划

动态规划,一般解题思路:

  1. 刻画一个最优解的结构特征。
  2. 递归的定义最优解的的值。
  3. 计算最优解的值,通常采用自底向上方法。
  4. 利用计算出的信息构造一个最优解。

按照以上步骤来解决这道题。
寻找最优子结构
找到最优子结构,然后利用这个子结构从子问题的最优解构造出原问题的最优解。

设匹配串S=s_1,s_2,...,s_m,模式串P=p_1,p_2,...,p_n,最终是否匹配成功记为isMatch,可看为布尔型。
1. 如果p_n’*’,若s_mp_n匹配,则isMatch为S_m1P_n1匹配的结果。
2. 如果p_n=’*’,若p_n1s_m匹配,则isMatch为S_mP_n1S_mP_n2S_m1P_n匹配结果进行或处理后的值。若不匹配,则isMatch为S_mP_n2匹配的结果。

递归解
用一个布尔类型的二维数组来建立最优解的递归式,通过上述,可以写成如下:

dp[i,j]=true dp[i1,j1] (dp[i,j1]||dp[i,j2]||dp[i1,j]) (dp[i,j2])i=0 & j=0i, j>0, p_n'\*',s_ip_ji, j>0, p_j='\*',s_ip_j1i, j>0, p_j='\*',s_ip_j1

计算
通过自底向上地计算。匹配问题共有m*n个子问题。
结果
直接获取二维数组最后的值,即为匹配的结果。
部分过程模拟示意图如下:


基础算法题-正则相关

动态规划解决代码如下:

boolean isMatchByDP(String s, String p) {
    if (p.isEmpty()) {
        return s.isEmpty();
    }
    int len_s = s.length(), len_p = p.length();
    //申请,默认为false
    boolean[][] dp = new boolean[len_s + 1][len_p + 1];
    dp[0][0] = true;
    //处理特殊情况,s为空的情况,例如 ""和".*"
    for (int i = 0; i < len_p; i++) {
        if (p.charAt(i) == '*' && dp[0][i - 1]) {
            dp[0][i + 1] = true;
        }
    }
    for (int i = 0; i < len_s; i++) {
        for (int j = 0; j < len_p; j++) {
            if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')
                dp[i + 1][j + 1] = dp[i][j];
            else if (p.charAt(j) == '*') {
                if (s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                    //出现一次,0次,出现多次
                    dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i + 1][j - 1] || dp[i][j + 1]);
                } else {
                    //出现0次
                    dp[i + 1][j + 1] = dp[i + 1][j - 1];
                }
            }
        }
    }
    return dp[len_s][len_p];
}

题二

阿里的笔试题,由题一简单变换下。’?’匹配每个字符,’*’匹配任意串。简单修改部分代码即可。

递归

递归解决如下:

boolean isMatch(String s, String p) {
    if (p.isEmpty()) {
        return s.isEmpty();
    }
    if (p.charAt(0) != '*') {
        if (s.isEmpty() || (p.charAt(0) != s.charAt(0) && p.charAt(0) != '?')) {
            return false;
        } else {
            return isMatch(s.substring(1), p.substring(1));
        }
    }
    while (!s.isEmpty() && (p.charAt(0) == '*')) {
        if (isMatch(s, p.substring(1))) {
            return true;
        }
        s = s.substring(1);
    }
    return isMatch(s, p.substring(1));
}
动态规划

动态规划解决如下:

boolean isMatch_dp(String p, String p) {
    if (p.isEmpty()) {
        return p.isEmpty();
    }
    boolean[][] dp = new boolean[p.length() + 1][p.length() + 1];
    dp[0][0] = true;
    for (int i = 0; i < p.length(); i++) {
        if (p.charAt(i) == '*' && dp[0][i])
            dp[0][i + 1] = true;
    }
   for (int i = 0; i < p.length(); i++) {
        for (int j = 0; j < p.length(); j++) {
            if (p.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
                dp[i + 1][j + 1] = dp[i][j];
            } else {
                if (p.charAt(j) == '*') {
                    //多次,一次
                    dp[i + 1][j + 1] = dp[i][j + 1] || dp[i][j];
                }
            }
        }
    }
    return dp[p.length()][p.length()];
}