LeetCode刷题系列 -- 10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

 
示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/regular-expression-matching
 

思路：大佬：经典动态规划：正则表达式 :: labuladong的算法小抄

思路：这道题还是有点难度的。
 1. 定义函数 dp((string)s, (string)p, (int)i, (int)j), 当 dp(s, p, i, j) == true 时，
     表示 s[i,...] 与 p[j,...] 是正则匹配的
 2. 对于任意的 i 与 j, s[i] 与 p[j] 有两种状态，要么匹配，要么不匹配
    伪代码如下：
    if s[i] == p[j] or p[j] = '.'  {  //  s[i] 与 p[j]相匹配时
         if j < p.size() - 1 and p[j+1] == '*' {
             // 对于 * ，则有两种情况，
             // 1. p[j]匹配 s 中的字符 0 次; 2. p[j] 匹配 s 中的字符多次
             bool is_metch_zero = dp(s, p, i, j+2); //  p[j]匹配 s 中的字符 0 次
             bool is_match_one_or_more = dp(s, p, i+1, j); // p[j] 匹配 s 中的字符多次
             return is_metch_zero || is_match_one_or_more;
         } else {
              // 当不是 * 时，不涉及到 匹配 0 次 或者多次
              return dp(s, p, i+1, j+1);
         }
    } else { // s[i] 与 p[j] 不相匹配时
         if j < p.size() - 1 and p[j+1] == '*' {
             return  dp(s, p, i, j+2); // 匹配 0次，继续往下看看
         } else {
             return false;
         }
    }
当然，迭代是指定通不过题目的case的，原因嘛，很简单，迭代会计算重复的 case。此时，
我们可以使用一个二维数组 memp 来记录 中途计算结果，避免重复计算 case。memp[i][j] 表示 s[i,...] 与 p[j,...] 是否正则匹配

java 代码如下：

class Solution {
 public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // 定义 map, key 为 图某个节点，value 为 (入度节点，权重值)
        // to -> (from, price)
        Map<Integer, List<int[]>> map = new HashMap<>();

        for (int[] dists : flights) {
            int from = dists[0];
            int to = dists[1];
            int price = dists[2];
            int[] subValue = {from, price};

            if (!map.containsKey(to)) {
                List<int[]> inValues = new LinkedList<>();
                inValues.add(subValue);
                map.put(to, inValues);
            } else {
                map.get(to).add(subValue);
            }
        }

        // 记录表，记录从 src 到 memp[i][j] 的最少花费且中转数为 j
        int[][] memp = new int[n][k + 1];

        for (int[] value : memp) {
            Arrays.fill(value, -888);
        }

        return dp(src, dst, k+1, map, memp);
    }

    int dp(int src, int dst, int k, Map<Integer, List<int[]>> map, int[][] memp) {
        if (dst == src) {
            return 0;
        }

        if (k == 0) {
            return -1;
        }

        int res = Integer.MAX_VALUE;
        // 当dst 有入度节点时
        if (map.containsKey(dst)) {
            for (int[] subValues : map.get(dst)) {
                int from = subValues[0];
                int price = subValues[1];

                int fromValue = memp[from][k - 1];

                if (fromValue == -888) {
                    fromValue = dp(src, from, k - 1, map, memp);
                    memp[from][k - 1] = fromValue;
                }

                if (fromValue != -1) {
                    res = Math.min(res, price + fromValue);
                }
            }
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }
}