动态规划:leetcode题库第四十四题
题号:44
难度:困难
题目描述:
给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串(包括空字符串)。
两个字符串完全匹配才算匹配成功。
说明:
s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。
示例:
输入:
输出:
原因:
输入:
输出:
原因:
思路:
方法:动态规划
正常匹配状态
?匹配状态
* 匹配状态
不匹配状态
还有一种情况,就是不匹配状态,这种其实跟匹配状态是一起判断的,都是根据当前状态和前一步判断得出结果
代码:
/**
* @author 孤磊
*/
public class Solution{
public boolean isMatch(String s, String p) {
String asterisk="*";
int sLen = s.length();
int pLen = p.length();
//Make a basic judgment
if (p.equals(s) || p.equals(asterisk)) {
return true;
}
if (p.isEmpty() || s.isEmpty()) {
return false;
}
//Create a new two-dimensional array DP. For better judgment, the length is string s and pattern P length + 1
boolean[][] dp = new boolean[pLen + 1][sLen + 1];
//Set DP [0] [0] position to true
dp[0][0] = true;
for(int pIdx = 1; pIdx < pLen + 1; pIdx++) {
//If the pattern character is *, and the previous position match is true, set the column to true, otherwise skip
if (p.charAt(pIdx - 1) == '*') {
int sIdx = 1;
//If the last match was false, move the pointer to the tail, which is skip
while ((!dp[pIdx - 1][sIdx - 1]) && (sIdx < sLen + 1)) {
sIdx++;
}
dp[pIdx][sIdx - 1] = dp[pIdx - 1][sIdx - 1];
while (sIdx < sLen + 1) {
dp[pIdx][sIdx++] = true;
}
}
//If the current match is?, the last match result will be copied to the current
else if (p.charAt(pIdx - 1) == '?') {
arraycopy(dp[pIdx - 1], 0, dp[pIdx], 1, sLen + 1 - 1);
} else {
//Get the current result based on the last matching result and the current matching result
for(int sIdx = 1; sIdx < sLen + 1; sIdx++) {
dp[pIdx][sIdx] = (p.charAt(pIdx - 1) == s.charAt(sIdx - 1) )&& dp[pIdx - 1][sIdx - 1];
}
}
}
System.out.print(" \t\t");
for (char ch:s.toCharArray()) {
System.out.print(ch+" \t");
}
System.out.println();
System.out.print("\t");
for (int i = 0; i < dp.length; i++) {
if (i!=0){
System.out.print(p.charAt(i-1)+"\t");
}
for (int j = 0; j < dp[i].length; j++) {
System.out.print(dp[i][j]+"\t");
}
System.out.println();
}
return dp[pLen][sLen];
}
}
时间复杂度:O(SP)
空间复杂度:O(SP)
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/wildcard-matching