程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Wildcard Matching

LeetCode Wildcard Matching

編輯:C++入門知識

LeetCode Wildcard Matching


LeetCode解題之Wildcard Matching


原題

萬用字符通配符的字符串匹配判斷。”?”表示一個任意的字符,”*”表示任意多個字符。判斷目標字符串是否與模式串相匹配。

注意點:

整個目標字符串要全部匹配進去,不能只匹配部分

例子:

輸入: s = “abc”, p = “a*b*e”

輸出: False

解題思路

與 Regular Expression Matching 同類型的題,不過換了不同類型的通配符。剛開始寫了一個動態規劃,結果超時了,轉換了下思路,改用回溯法。用兩個指針分別來表示目標串和模式串遍歷到的當前位置,如果兩個字符相等(考慮”?”通配符),則繼續前進,如果是”*”通配符,那麼要記錄下目標字符串當前位置,及模式串下一個位置,現在假設的是”*”用來匹配0個字符,繼續嘗試匹配,如果後面出現不匹配的情況,那麼應該回退到這兩個位置(目標串的位置要向後移一位,否則會不斷回退到原來的位置),發生一次回退,代表著”*”要多匹配掉一個字符。按照這種方式不斷嘗試匹配,直到目標串都已經匹配掉或者匹配失敗(匹配串中沒有”*”,且不能匹配整個目標串)。這時候要看看匹配串是否還有剩余除了”*”以外的字符。如果最終匹配串都全部遍歷完了,那麼說明匹配成功。

AC源碼

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        p_index, s_index, last_s_index, last_p_index = 0, 0, -1, -1
        while s_index < len(s):
            # Normal match including '?'
            if p_index < len(p) and (s[s_index] == p[p_index] or p[p_index] == '?'):
                s_index += 1
                p_index += 1
            # Match with '*'
            elif p_index < len(p) and p[p_index] == '*':
                p_index += 1
                last_s_index = s_index
                last_p_index = p_index
            # Not match, but there is a '*' before
            elif last_p_index != -1:
                last_s_index += 1
                s_index = last_s_index
                p_index = last_p_index
            # Not match and there is no '*' before
            else:
                return False
        # Check if there is still character except '*' in the pattern
        while p_index < len(p) and p[p_index] == '*':
            p_index += 1
        # If finish scanning both string and pattern, then it matches well
        return p_index == len(p)


if __name__ == "__main__":
    assert Solution().isMatch("aa", "a") == False
    assert Solution().isMatch("aa", "aa") == True
    assert Solution().isMatch("aaa", "aa") == False
    assert Solution().isMatch("aa", "*") == True
    assert Solution().isMatch("aa", "a*") == True
    assert Solution().isMatch("ab", "?*") == True
    assert Solution().isMatch("aab", "c*a*b") == False

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved