Leetcode#44 Wildcard Matching

type
status
date
slug
summary
tags
category
icon
password
*代表任意长度的任意字符
?代表任意字符
需要实现这个匹配逻辑。现在有字符串s和匹配模版p，要求判断p是否能完全匹配s
 

思路

从左到由遍历p，可以这样匹配
  • 如果该字符为固定字符，就能找到这个字符在s中的所有下标
  • 如果该字符为*，匹配任意长度0-MAX
  • 如果该字符为?，匹配任意长度1
优化一下
** = * ⇒ 匹配长度 0-MAX
*? = ?* ⇒ 匹配长度1-MAX
ab ⇒ 满足s.indexOf(a)+1 = s.indexOf(b)
a?b ⇒ 满足s.indexOf(a)+2 = s.indexOf(b)
a???b ⇒ 满足s.indexOf(a)+4 = s.indexOf(b)
a*b ⇒ 满足s.indexOf(a) ≤ s.indexOf(b)
a?*b = a*?b ⇒ 满足s.indexOf(a)+1 ≤ s.indexOf(b)
除了*，其他字符串都是长度固定的，所以我们可以将p视为用*连接的多个子字符串
需要满足，
  1. s.indexOf(str1)≤s.indexOf(str2)≤s.indexOf(str3)≤s.indexOf(str4)
  1. len(str1)+len(str2)+len(str3)+len(str4) ≤ len(s)
再经过一点点小优化，就成了这样子：
Loading...

© XGFan 2012-2025