Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
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 = "a*"
**Output:** true
**Explanation:** '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
**Input:**
s = "ab"
p = ".*"
**Output:** true
**Explanation:** ".*" means "zero or more (*) of any character (.)".
Example 4:
**Input:**
s = "aab"
p = "c*a*b"
**Output:** true
**Explanation:** c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
**Input:**
s = "mississippi"
p = "mis*is*p*."
**Output:** false
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 <font face="monospace">?</font> 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 = “ab” Output: true Explanation: The first ‘‘ matches the empty sequence, while the second ‘‘ matches the substring “dce”.
key为子问题索引st，value为子问题的解。不含path和res因为类似于Catalan，用子问题返回结果来组成此轮结果。f(input, st, endIndex, cache) -> List
紧跟终结条件，若在cache中，返回子问题的解。
循环结束，将子问题的结果存于cache。
注意事项：
cache是一个解的集合，所以终止条件返回也需要是一个list
Python代码：
1 2 3 4 5 6 7 8 9 10 11
defdfs(self, input, cache) -> List[int]: if <终止条件>: return [] # remember to use list if input in cache: return cache[input] res = [] for i in range(len(input)): anwser = self.dfs(input[:i], cache) res.append(anwser) cache[input] = res return res
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = “catsanddog“ wordDict = ["cat", "cats", "and", "sand", "dog"] Output:[
"cats and dog",
"cat sand dog"
]
Example 2:
Input: s = “pineapplepenapple” wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”] Output: [ “pine apple pen apple”, “pineapple pen apple”, “pine applepen apple” ] Explanation: Note that you are allowed to reuse a dictionary word.
defwordBreak(self, s: str, wordDict: List[str]) -> List[str]: wordSet = set() for word in wordDict: wordSet.add(word) cache = {} res = self.dfs(s, wordSet, cache) return [] if len(res) == 1andnot res[0] else res
defdfs(self, s, wordSet, cache): ifnot s: return [''] if s in cache: return cache[s] res = [] for i in range(len(s)): if s[:i + 1] notin wordSet: continue li = self.dfs(s[i + 1:], wordSet, cache) for ss in li: res.append((s[:i + 1] + ' ' + ss).strip())
