#LeetCode:44. Wildcard Matching

灆洢 2019-04-11 21:27:56

以「*」作為分隔,可以將 Pattern 切成好幾段,由於中間是「*」的關係,這幾段中間可以間隔任意數量的字元,並且除最後一段外的前面所有段都是盡量越前面有配對到就選最前面可以配對的地方即可,直接配到最後一段就要配對完成最後面即可。

C++(12ms)

/*******************************************************/
/* LeetCode 44. Wildcard Matching                      */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2019/04/11                                 */
/*******************************************************/
#include <string>
using namespace std;

class Solution {
public:
  bool isMatch(string s, string p) {
    int sIndex = 0;
    int pIndex = 0;
    int lastStarFirstSIndex = -1;
    int lastStarPIndex = -1;

    while(sIndex < s.length()){
      if(pIndex < p.length() && p[pIndex] == '*'){
        lastStarFirstSIndex = sIndex;
        lastStarPIndex = pIndex;
        ++pIndex;
      }
      else if(pIndex < p.length() && (s[sIndex] == p[pIndex] || p[pIndex] == '?')){
        ++sIndex;
        ++pIndex;
      }
      else if(lastStarPIndex != -1){
        ++lastStarFirstSIndex;
        sIndex = lastStarFirstSIndex;
        pIndex = lastStarPIndex + 1;
      } 
      else return false;
    }

    while(pIndex < p.length()){
      if(p[pIndex] != '*') return false;
      ++pIndex;
    }

    return true;
  }
};

在〈“#LeetCode:44. Wildcard Matching”〉中有 1 則留言

#生活趣事:[19.04.08~19.04.14]-初次體驗加分 100% 與初次參與遊戲二創繪圖活動 - 翼世界夢想領域 發表迴響 取消回覆

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料