问题简介： 给定输入字符串和模式p,实现通配符模式匹配并支持规则’？’ 和’’ 注： 1.’?’ 匹配任意一个字符 2.’ * ’ 匹配任意一个字符串包括空字符串 3.要两个字符串完全匹配而不是部分匹配 举例： 1: 输入: s = “aa” p = “a” 输出: false 解释: “a” 不完全匹配字符串 “aa”. 2: 输入: s = “aa” p = " * " 输出: true Explanation: ’ * ’ 匹配任意字符串 3: 输入: s = “cb” p = “?a” 输出: false 解释: ‘?’ 匹配 ‘c’, 但第二个字符 ‘a’不匹配 ‘b’. 4: 输入: s = “adceb” p = “ab” 输出: true 解释: 第一个’ * ’ 匹配为空字符串,第二个 ’ * ’ 匹配字符串"dce". 5: 输入: s = “acdcb” p = "ac?b" 输出: false 解法一：Time Limit Exceeded 我第一次想到的是递归的做法,在输入字符串较少的情况下没问题,字符串很长的时候就不行了
class Solution { public boolean isMatch(String s, String p) { if(p.isEmpty())return s.isEmpty(); boolean firstMatch = (!s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '?')); if(p.length() == 1 && p.charAt(0) == '*')return true; if(p.charAt(0) == '*'){ if(s.length() < 1)return isMatch(s,p.substring(1)); else return ( isMatch(s.substring(1),p) || isMatch(s,p.substring(1))); } else return firstMatch && isMatch(s.substring(1),p.substring(1)); } }解法二： 让我们在这里使用两个指针:s_idx迭代字符串,p_idx迭代模式,而s_idx <s_len： 如果模式p_idx <p_len中仍然存在字符,并且指针下的字符与p [p_idx] == s [s_idx]或p [p_idx] ==’？‘匹配,则通过增加两个指针来向前移动, 否则,如果模式p_idx <p_len和p [p_idx] ==’*'中仍有字符,则首先检查“匹配零字符”情况,即仅增加模式指针p_idx ++,记下可能回溯star_idx变量中的星位置,以及s_tmp_idx变量中的当前字符串指针. 如果模式中没有星号,即没有star_idx,则返回False. 如果有一个星,那么回溯:在最后一个星p_idx = star_idx + 1之后设置模式指针,并且字符串指针s_idx = s_tmp_idx + 1,即假设这次星与另一个字符匹配,保存当前字符串指针以查找可能的回溯s_tmp_idx = s_idx. 如果模式中的所有剩余字符都是星号,则返回True
class Solution { public boolean isMatch(String s, String p) { int sLen = s.length(), pLen = p.length(); int sIdx = 0, pIdx = 0; int starIdx = -1, sTmpIdx = -1; while (sIdx < sLen) { if (pIdx < pLen && (p.charAt(pIdx) == '?' || p.charAt(pIdx) == s.charAt(sIdx))){ ++sIdx; ++pIdx; } else if (pIdx < pLen && p.charAt(pIdx) == '*') { starIdx = pIdx; sTmpIdx = sIdx; ++pIdx; } else if (starIdx == -1) { return false; } else { pIdx = starIdx + 1; sIdx = sTmpIdx + 1; sTmpIdx = sIdx; } } for(int i = pIdx; i < pLen; i++) if (p.charAt(i) != '*') return false; return true; } }小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海
