Regular Expression Matching (H)
Given an input string (s) and a pattern (p), 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).
Note:
scould be empty and contains only lowercase lettersa-z.pcould be empty and contains only lowercase lettersa-z, and characters like.or*.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
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:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
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:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
題意
實作一個包含'.'、'*'的正則匹配判定，
思路
遞回法：
遞回邊界為，當p空時，若s非空則回傳false，若s空則回傳true，(反過來s空p非空時無法作為邊界，因為如果s為空，p為 ".*"，則同樣滿足匹配)，
當p的第二位不為 '*' 時，如果當前s和p的第一位匹配，那么只要遞回判斷isMatch(s.subString(1), p.subString(1))即可；
當p的第二位為 '*' 時，說明要對p的第一位字符進行多次匹配判斷，這里可以分為兩種情況 (記 '*' 前字符為x)：1. s的第一位與x匹配，遞回判斷s第一位之后的子字串是否與p匹配 (因為 "x*" 表示x可以出現0次或多次，所以每次遞回可以理解為去除了一個匹配的x)；2. s的第一位與x不匹配，但與 '*' 后的第一個字符匹配，或者s的第一位既與x匹配，也與 '*' 后的第一個字符匹配，那么要判斷s是否與 "x*" 之后的正則運算式相匹配，以上兩種情況滿足其一即可說明匹配成功，
記憶化搜索：
可以看到，在遞回的程序中存在著許多重復的計算(即相同的s和p子串出現了多次)，因此可以用一個陣列將中間狀態保存下來，
動態規劃：
參考 [LeetCode] 10. Regular Expression Matching 正則運算式匹配
代碼實作
Java
遞回
class Solution {
public boolean isMatch(String s, String p) {
// 遞回邊界，只能以p空為判斷點
if (p.isEmpty()) {
return s.isEmpty();
}
boolean isFirstMatch = (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));
if (p.length() >= 2 && p.charAt(1) == '*') {
return ((isFirstMatch && isMatch(s.substring(1), p)) || isMatch(s, p.substring(2)));
} else {
return isFirstMatch && isMatch(s.substring(1), p.substring(1));
}
}
}
記憶化搜索優化
class Solution {
public boolean isMatch(String s, String p) {
return isMatch(s, 0, p, 0, new int[s.length() + 1][p.length() + 1]);
}
private boolean isMatch(String s, int sHead, String p, int pHead, int[][] record) {
if (pHead == p.length()) {
return sHead == s.length();
}
if (record[sHead][pHead] != 0) {
return record[sHead][pHead] == 1 ? true : false;
}
boolean matched = false;
boolean firstMatch = sHead < s.length() && (s.charAt(sHead) == p.charAt(pHead) || p.charAt(pHead) == '.');
if (pHead < p.length() - 1 && p.charAt(pHead + 1) == '*') {
matched = firstMatch && isMatch(s, sHead + 1, p, pHead, record) || isMatch(s, sHead, p, pHead + 2, record);
} else {
matched = firstMatch && isMatch(s, sHead + 1, p, pHead + 1, record);
}
record[sHead][pHead] = matched ? 1 : -1;
return matched;
}
}
動態規劃
class Solution {
public boolean isMatch(String s, String p) {
boolean dp[][] = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int i = 0; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (j > 1 && p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2] || i > 0 && dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.');
} else {
dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
}
}
}
return dp[s.length()][p.length()];
}
}
JavaScript
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function (s, p) {
if (p.length === 0) {
return s.length === 0
}
let firstMatch = s.length !== 0 && (s[0] === p[0] || p[0] === '.')
if (p.length >= 2 && p[1] === '*') {
return (firstMatch && isMatch(s.slice(1), p)) || isMatch(s, p.slice(2))
} else {
return firstMatch && isMatch(s.slice(1), p.slice(1))
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/43516.html
標籤：其他