# 字符串匹配

## Wildcard Matching

* 首先想DFS暴力解法的recursion递归的拆解逻辑，不要一上来就想DP
* 这题提供两种wildcard

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

* 重点就在"\*", 可以match 0 or more chars, 那就分成两种情况讨论
  * match 0 char, then return isMatch(s, sIndex, p, pIndex + 1)
  * match at least 1 char, then return isMatch(s, sIndex + 1, p, pIndex)
* 定义好了递归3要素，至少可以写出DFS brute force solution
* 这里可以用memoization做优化实现o(m\*n) Time, o(m\*n) Space

```
class Solution {
    /*
    "abcab" and "*a*b"
    p is allStar "***"
    isMatch(s, sIndex, p, pIndex)
    
    pIndex == sIndex -> return isMatch(s, sIndex + 1, p, pIndex + 1)
    pIndex == ? -> return isMatch(s, sIndex + 1, p, pIndex + 1)
    group into same isCharMatch(sChar, pChar)
    
    pIndex == * -> return isMatch(s, sIndex, p, pIndex + 1) || isMatch(s, sIndex + 1, p, pIndex)
    
    use memoization to avoid duplicate calculation
    boolean[m][n] visited
    boolean[m][n] memo
    
    O(m * n) Time
    O(m * n) Space
    
    */
    
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
        int m = s.length(), n = p.length();
        //use memoization to avoid duplicate calculation
        boolean[][] visited = new boolean[m][n];
        boolean[][] memo = new boolean[m][n];
        return isMatch(s, 0, p, 0, visited, memo);
    }
    
    //definition of recursion: check whether s.substring(sIndex) and p.substring(pIndex) can be a match or not
    private boolean isMatch(String s, int sIndex, String p, int pIndex, boolean[][] visited, boolean[][] memo) {
        //base case
        if (pIndex == p.length()) {
            return sIndex == s.length() ;
        }
        if (sIndex == s.length()) {
            return isAllStar(p, pIndex);
        }
        //fetch from memo
        if (visited[sIndex][pIndex]) {
            return memo[sIndex][pIndex];
        }
        //transition
        char sChar = s.charAt(sIndex), pChar = p.charAt(pIndex);
        if (pChar == '*') {
            memo[sIndex][pIndex] =  isMatch(s, sIndex, p, pIndex + 1, visited, memo) ||  isMatch(s, sIndex + 1, p, pIndex, visited, memo);
        } else {
            memo[sIndex][pIndex] = isCharMatch(sChar, pChar) && isMatch(s, sIndex + 1, p, pIndex + 1, visited, memo);
        }
        
        //set memo
        visited[sIndex][pIndex] = true;
        return memo[sIndex][pIndex];
    }
    private boolean isAllStar(String p, int idx) {
        for (int i = idx; i < p.length(); i++) {
            if (p.charAt(i) != '*') {
                return false;
            }
        }
        return true;
    }
    private boolean isCharMatch(char sChar, char pChar) {
        return sChar == pChar || pChar == '?';
    }
}
```

## Regular Expression Matching

* 做完wildcard matching之后再做这题思路就清晰很多了
* 和 Wildcard Matching 同样模板的代码, 只需要更改“\*“ 的matching logic,就好
* &#x20;'\*' Matches zero or more of the preceding element.
* '\*' 不会单独出现或者出现在首位
* 需要把'\*'和前面的char连起来看， ‘‘c\*a\*b" -> "c\*", 不能直接判断'\*' char

```
class Solution {
    /*
    "abcab" and "c*a*b" -> '*' 不会单独出现或者出现在首位
    isMatch(s, sIndex, p, pIndex)
    
    pIndex == sIndex -> return isMatch(s, sIndex + 1, p, pIndex + 1)
    pIndex == . -> return isMatch(s, sIndex + 1, p, pIndex + 1)
    group into same isCharMatch(sChar, pChar)
    
    遇到'*'不能单独处理，需要跟之前的char一起处理'a*'
    '"a*", 小技巧, pIndex point to 'a', 判断pIndex + 1是否是*
    pIndex + 1 == * -> return isMatch(s, sIndex, p, pIndex + 2) || (sameChar(sChar, pChar) & isMatch(s, sIndex + 1, p, pIndex))
    
    use memoization to avoid duplicate calculation
    boolean[m][n] visited
    boolean[m][n] memo
    
    O(m * n) Time
    O(m * n) Space
    
    */
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
        int m = s.length(), n = p.length();
        //use memoization to avoid duplicate calculation
        boolean[][] visited = new boolean[m][n];
        boolean[][] memo = new boolean[m][n];
        return isMatch(s, 0, p, 0, visited, memo);
    }
    
    //definition of recursion: check whether s.substring(sIndex) and p.substring(pIndex) can be a match or not
    private boolean isMatch(String s, int sIndex, String p, int pIndex, boolean[][] visited, boolean[][] memo) {
        //base case
        if (pIndex == p.length()) {
            return sIndex == s.length() ;
        }
        if (sIndex == s.length()) {
            return isEmpty(p, pIndex);
        }
        //fetch from memo
        if (visited[sIndex][pIndex]) {
            return memo[sIndex][pIndex];
        }
        //transition
        char sChar = s.charAt(sIndex), pChar = p.charAt(pIndex);
        if (pIndex + 1 < p.length() && p.charAt(pIndex + 1) == '*') {
            memo[sIndex][pIndex] =  isMatch(s, sIndex, p, pIndex + 2, visited, memo) ||  isCharMatch(sChar, pChar) && isMatch(s, sIndex + 1, p, pIndex, visited, memo);
        } else {
            memo[sIndex][pIndex] = isCharMatch(sChar, pChar) && isMatch(s, sIndex + 1, p, pIndex + 1, visited, memo);
        }
        
        //set memo
        visited[sIndex][pIndex] = true;
        return memo[sIndex][pIndex];
    }
    private boolean isEmpty(String p, int idx) {
        for (int i = idx; i < p.length(); i+= 2) {
            if (i + 1 >= p.length() || p.charAt(i + 1) != '*') {
                return false;
            }
        }
        return true;
    }
    private boolean isCharMatch(char sChar, char pChar) {
        return sChar == pChar || pChar == '.';
    }
}
```

## Word Break

* state:canBreak\[i] means whether sb.substring(0, i) can be break&#x20;
* canBreak\[i] = dict.contains(s.susbtring(j, i)) && canBreak\[j]
* i from \[1, n]
* j from \[0, i)
* return canBreak\[n]

```
class Solution {
    /*
    state:canBreak[i] means whether sb.substring(0, i) can be break
    canBreak[i] = dict.contains(s.susbtring(j, i)) && canBreak[j]
    i from [1, n]
    j from [0, i)
    
    initial:
    canBreak[0] = true
    
    res:
    return canBreak[n]
    */
    
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> dict = new HashSet<>();
        for (String word : wordDict) {
            dict.add(word);
        }
        boolean[] canBreak = new boolean[n + 1];
        canBreak[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dict.contains(s.substring(j, i)) && canBreak[j]) {
                    canBreak[i] = true;
                    break;
                }
            }
        }
        return canBreak[n];
    }
}
```

## Word Break II

* same idea of wordBreak, use memo to avoid duplicate calculation
* use Map for memo, key is string, value is List\<String> that can be break for key
* optimization: get maxLen of word in wordDict, then we just need to iterate for length of maxLen instead of iterate through whole string s.

```
class Solution {
    /*
    same idea of wordBreak, use memo to avoid duplicate calculation
    use Map for memo, key is string, value is List<String>
    
    optimization: get maxLen of word in wordDict, then we just need to iterate for length of maxLen instead of iterate through whole string s.
    */
    
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>();
        int maxLen = 0;
        for (String word : wordDict) {
            dict.add(word);
            maxLen = Math.max(maxLen, word.length());
        }
        return helper(s, dict, new HashMap<String, List<String>>(), maxLen);
    }
    //return all result for string s
    private List<String> helper(String s, Set<String> dict, Map<String, List<String>> memo,int maxLen) {
        if (memo.containsKey(s)) {
            return memo.get(s);
        }
        List<String> res = new ArrayList<>();
        if (s.length() == 0) return res;
        for (int i = 1; i <= maxLen && i <= s.length(); i++) {
            String word = s.substring(0, i);
            if (!dict.contains(word)) continue;
            if (i == s.length()) {
                res.add(word);
                break;
            } else {
                String suffix = s.substring(i);
                List<String> segmentations = helper(suffix, dict, memo, maxLen);
                for (String segmentation : segmentations) {
                    res.add(word + " " + segmentation);
                }
            }
        }
        memo.put(s, res);
        return res;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://syjohnson11.gitbook.io/leetcode/7_dp/er-wei-dp.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.