首页 > 代码库 > 44. Wildcard Matching
44. Wildcard Matching
之前就写过了，但是没有在这写，今天重新写了一遍。
两个指针，一个维持pattern的位置，一个维持str的位置，每一次循环str的idx或者pattern的idx至少有一个会往后移动一步。
当strIdx < srtLen的时候
因为存在*这个pattern所以要进行尝试，加入*匹配0个、1个、2个..试试看能不能匹配到最后，方法是记录上次遇到*的时候的PatternIdx和strIdx，如果后面没有匹配上，那么strIdx就从下一个开始匹配，patternIdx不变。
如果没有匹配上，然后又没有上一个*，那么就匹配失败
最后结束了以后，因为到这里的时候str一定已经结束了pattern可能有剩下的*，也要处理掉，最后返回pattenIdx == patternLen，是不是pattern也可以用完
1 public boolean isMatch(String s, String p) { 2 if(s == null || p == null) { 3 return false; 4 } 5 int i = 0; 6 int j = 0; 7 int sLen = s.length(); 8 int pLen = p.length(); 9 int lastPatternIdx = -1;10 int lastStrIdx = -1;11 while(i < s.length()) {12 if(j < pLen && (s.charAt(i) == p.charAt(j) || p.charAt(j) == ‘?‘)) {13 i++;14 j++;15 } else if(j < pLen && p.charAt(j) == ‘*‘) {16 lastPatternIdx = j;17 lastStrIdx = i;18 j++;19 } else if(lastPatternIdx != -1) {20 i = ++lastStrIdx;21 j = lastPatternIdx + 1;22 } else {23 return false;24 }25 }26 while(j < pLen && p.charAt(j) == ‘*‘) {27 j++;28 }29 return j == pLen;30 }
我觉得最差的情况是O(m*n)，比如pattern是“aaaaaaaab”，但是str是“aaaaaaaaaaaaaa”，每次pattern匹配到最后一位都要往前跳
44. Wildcard Matching
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。