字符串匹配

矩阵类的题目能用DFS解答的都要想到memoization来优化，Tree则不能用memo优化

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,就好
'*' 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
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;
    }
}

Previous一维DP Next8. Data Structure

Last updated 5 years ago

Was this helpful?