0%

Analysis of LeetCode High Frequency Problems III

Posted on Edited on In
Symbols count in article: 2.4k

详细讲解LeetCode考察较多的3道题目：10、84、28。

10.Regular Expression Matching(正则表达式匹配)(Hard)

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

1
2
'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

1
2
3
4
5
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

1
2
3
4
5
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

1
2
3
4
5
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

1
2
3
4
5
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

1
2
3
4
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

解：如果可以调库，可以利用String的matches方法来判断即可：

1
2
3
4
5
class Solution {
    public boolean isMatch(String s, String p) {
        return s.matches(p);
    }
}

但是上面的操作其实更像是一个玩笑(^_^)

这道题是可以用动态规划解决的经典问题，用动态规划自底向上地解决这道题，可以避免在过程中产生的重复的计算过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null || p == null) return s.equals(p);
        
        int m = s.length(), n = p.length();
        
        // 状态dp[i][j]表示s的前i个能否被p的前j个匹配
        boolean[][] dp = new boolean[m+1][n+1];
        //初始化dp[0][0]等于true,表示当两字符串长度都为0，也就是空
        // 字符串时，他们互相匹配
        dp[0][0] = true;
        
        // 最重要的步骤之一
        // 初始化二维矩阵第一列所有值：
        // 当s为空字符串时，对p字符串的任一位置，要使得这个位置的子串能和空字符串匹配，
        // 要求，这个子串都是由一系列的型号组合构成
        for(int j = 1; j <= n; j++) {
            // 注意因为申请boolean数组是长度+1，所以p的charAt位置和j的位置相差1，即j-1位置是p.charAt的位置
            dp[0][j] = j > 1 && p.charAt(j-1) == '*' && dp[0][j-2];
        }
        
        // 接下来就是给这个二维矩阵填表了,逻辑和递归一模一样
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                // p的当前字符不是星号(*)时，判断当前两字符是否相等，如果相等，则看看dp[i-1][j-1]的值，
                // 因为它保存了前一个匹配的结果
                if(p.charAt(j - 1) != '*') {
                    dp[i][j] = dp[i-1][j-1] && isMatch(s.charAt(i - 1), p.charAt(j-1));
                } else {
                    // 当p当前字符是星号(*)时,进行两种尝试：
                    // -用星号组合表示空字符串，看看是否能匹配，即dp[i][j-2]
                    // -用星号组合表示一个字符，看看是否能匹配，即dp[i-1][j]
                    dp[i][j] = dp[i][j-2] || dp[i-1][j] && isMatch(s.charAt(i-1),p.charAt(j-2));
                }
            }
        }
        return dp[m][n];
    }
     
    boolean isMatch(char a, char b) {
        return a == b || b == '.';
    }
}

动态规划方法的复杂度：

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n^2)

84.Largest Rectangle in Histogram(柱状图中最大的矩形)(Hard)

28.implement-strstr(实现strStr())(Easy)