题目链接：点击打开链接
题目大意：略。
解题思路
相关企业
- 字节跳动
- 苹果（Apple）
- 微软（Microsoft）
- 谷歌（Google）
- 英伟达（NVIDIA）
- 亚马逊（Amazon）
AC 代码
- Java
class Solution { public boolean isMatch(String s, String p) { int m = s.length() + 1, n = p.length() + 1; boolean[][] dp = new boolean[m][n]; dp[0][0] = true; for(int j = 2; j < n; j += 2) dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*'; for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { dp[i][j] = p.charAt(j - 1) == '*' ? dp[i][j - 2] || dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') : dp[i - 1][j - 1] && (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1)); } } return dp[m - 1][n - 1]; } }
- C++
class Solution { public: bool isMatch(string s, string p) { int m = s.size() + 1, n = p.size() + 1; vector<vector<bool>> dp(m, vector<bool>(n, false)); dp[0][0] = true; for(int j = 2; j < n; j += 2) dp[0][j] = dp[0][j - 2] && p[j - 1] == '*'; for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { dp[i][j] = p[j - 1] == '*' ? dp[i][j - 2] || dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'): dp[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]); } } return dp[m - 1][n - 1]; } };
