【LeetCode】044. Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.



Example 1:

Input: s = "aa"  p = "a"
Output: False
Explanation: "a" does not match the entire string "aa".



Example 2:

Input: s = "aa"  p = "*"
Output: True
Explanation: '*' matches any sequence.



Example 3:

Input: s = "cb"  p = "?a"
Output: False
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.



Example 4:

Input: s = "adceb" p = "*a*b"
Output: True
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".



Example 5:

Input: s = "acdcb" p = "a*c?b"
Output: False


解題邏輯與實作

有點像是第十題的Regular Expression Matching,不過符號的意義不太一樣,這邊使用的?表示一個萬用字元,*則是表示多個萬用字元。


遞迴

跟Regular Expression相比最大的差異應該是*的用法。在Regular Expression中*不可能單獨存在,必定會跟跟在某個字元後面,在產生subpattern時要特別注意;但在這題中*可以單獨存在,subpattern應該只有pattern或pattern[1:]兩種。

  1. 若pattern為空字串,則檢查string是否為空字串
    1. 是,則回傳 True
    2. 否,則回傳 False
  2. 檢查string是否為空字串
    1. 是,判斷pattern是否為*
      1. 是,呼叫遞迴傳入string與pattern[1:]
      2. 否,則回傳 False
    2. 否,向下執行
  3. pattern的字首與string的字首是否匹配(匹配情況包含pattern字首為?*的情況)
    1. 是,判斷pattern是否為*
      1. 是,則呼叫遞迴傳入分別傳入string[1:]與pattern和string[1:]與pattern[1:]
      2. 否,則呼叫遞迴傳入string[1:]與pattern[1:]
    2. 否,則回傳 False



一樣多加了參數暫存比較結果,節省呼叫次數。不過按照上面那個邏輯去寫在遇到這個testcase時會Memory Limit Exceeded,所以修改了第二個判斷式的邏輯,判斷pattern扣除掉*長度:

  1. 若pattern扣除掉*長度為0,則回傳True
    • 代表pattern剩下的整句都是*,因此不用管string內容是什麼一定會匹配。
  2. 若pattern扣除掉*長度大於string的長度,則回傳False
    • 也就是即便*全用來匹配空字串,仍會有部份pattern無法匹配上string,因為除*外的pattern符號都必須匹配一個字元,但目前pattern比string還長…
    • 另外string長度等於0的case,也包含在這,因此原先判斷式中對於string長度為0的case可以全刪除了。



程式碼

class Solution:
	def __init__(self):
		self.memo = {}

	def isMatch(self, s, p):
		if (s,p) in self.memo:
			return self.memo.get((s,p))

		p_len = len(p)
		s_len = len(s)
		sub_p_len = len(p.replace("*",""))
     
		if p_len == 0:
			return s_len == 0

		if sub_p_len == 0 :
			return True
	
		if sub_p_len > s_len:
			self.memo[(s,p)] = False
			return False

		result = False
		if p[0]=='?' or p[0]=='*' or p[0] == s[0]:
			if p[0] == '*':    
				result = self.isMatch(s[1:] , p) or self.isMatch(s , p[1:])
			result = result or self.isMatch(s[1:] , p[1:]) 

		self.memo[(s,p)] = result
		return result

總算可以過了,但說實話效能不是很好跑出了1096 ms、40.91 %的成績,還有非常大的改進空間。


雙指標

原本是在找Dynamic Programming的解法,但連續找到兩篇說用DP會TLE,說要改用雙指標回朔,所以我決定也來寫寫看:

  1. 初始化兩個指標s_index與p_index,分別指向string與pattern的字首
  2. 判斷s_index是否小於string長度
      1. 若指標位置可以匹配(匹配情況包含pattern為?,但排除為*的情況),兩個指標皆向後移動
      2. 若pattern目前指向為*,則pattern指標向後移動,並記下目前指標位置(last_s_index與last_p_index)
        • 先假設*匹配的是空字元的情況,向後進行匹配,
      3. 假設*匹配空字元狀況下,無法完成整句匹配,因此所紀錄的位置,且last_s_index加一
        • 表示它匹配了*,因此可以不再考慮
      4. 若上述的Case皆無法匹配,則為回傳False
    1. 否,向下執行
  3. 在掃完string後,檢查pattern是否還有剩下除*外的字元
    1. 有,表示未完成匹配,回傳False
    2. 無,則回傳True



程式碼

class Solution(object):
	def isMatch(self, s, p):
		"""
		:type s: str
		:type p: str
		:rtype: bool
		"""
		s_len, p_len = len(s), len(p)
		s_idx, p_idx = 0, 0
		last_s_idx, last_p_idx = -1, -1

		while s_idx < s_len:
			if p_idx < p_len and (p[p_idx]=='?' or p[p_idx]==s[s_idx]):
				s_idx += 1
				p_idx += 1
			elif p_idx < p_len and p[p_idx]=='*' :
				p_idx += 1
				last_s_idx, last_p_idx = s_idx , p_idx 
			elif last_p_idx != -1 :
				last_s_idx += 1
				s_idx, p_idx = last_s_idx, last_p_idx
			else:
				return False
		
		return len(p[p_idx:].replace("*","")) == 0

效能好上不少,136 ms、 83.93%



是說看標籤應該還可以用Dynamic Programming跟Greedy Algorithm來解題,先欠著回頭再來研究XD



[LeetCode] 解題目錄 -> 這裡走

留言

這個網誌中的熱門文章

用Markdown寫Blogger文章

【Vue.js 學習筆記】02. 基礎 Vue 概述