String

10. Regular Expression Matching

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).

"""
先想只有 . 的情形, either s[i] == (p[i] || .)
再想 '*' 的兩種情況
1. repeat * 之前的char
2. ignore * 之前的char

Corner case
s: aa, a, ''
p: a* <- all valid

s為空, p 可不為空

"""

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p:
            return not s
        
        first_match = s and p[0] in (s[0], '.')
        
        if len(p) >=2 and p[1] == '*':
            return self.isMatch(s, p[2:]) or \
            (first_match and self.isMatch(s[1:], p))
            
        else:
            return first_match and self.isMatch(s[1:], p[1:])

44. 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).

class Solution:
    """
1. 假如 p[j-1] == '?'，则dp[i][j] = dp[i-1][j-1]
2. 假如 p[j-1] == letter(a-zA-Z)，则dp[i][j] = dp[i-1][j-1] && (s[i-1]==p[j-1])
3. 假如 p[j-1] == '*',则 dp[i][j] = dp[i-1][j] || dp[i][j-1]
    3.1 dp[i-1][j] 代表'*'為空
    3.2 dp[0][j-1] - dp[i-1][j-1] 有一為真即可, 所有結果包含在dp[i][j-1]
    """
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m+1)]
        
        dp[0][0] = True
        
        # corner case: pattern = '*****'
        for j in range(1, n+1):
            if p[j-1] == '*':
                dp[0][j] = dp[0][j-1]
                
        for i in range(1, m+1):
            for j in range(1, n+1):
                if p[j-1] == '?':
                    dp[i][j] = dp[i-1][j-1]
                elif p[j-1] == '*':
                    dp[i][j] = dp[i][j-1] or dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j-1] and s[i-1] == p[j-1]
        
        return dp[m][n]

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

"""
idx1 相乘 idx2 會落在 idx1+idx2, idx1+idx2+1
reverse string 會比較好做
"""
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        size1, size2 = len(num1), len(num2)
        result = [0] * (size1+size2)
        num1 = num1[::-1]
        num2 = num2[::-1]
        
        carry = 0
        for i1, n1 in enumerate(num1):
            for i2, n2 in enumerate(num2):
                num = int(n1)*int(n2)
                idx = i1+i2
                carry, result[idx] = divmod(result[idx]+num, 10) 
                carry, result[idx+1] = divmod(result[idx+1]+carry, 10)
                if carry:
                    result[idx+2] +=1
        num = 0
        for n in result[::-1]:
            num = num*10 + n
            
        return str(num)

205 Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

 def isIsomorphic(self, s: str, t: str) -> bool:
    if len(s) != len(t): return False
    dic = defaultdict(int)
    
    for i in range(len(s)):
        cs = s[i]
        ct = t[i]
        if cs in dic:
            if dic[cs] != ct: return False
        else:
            if ct in dic.values():
                return False
            else:
                dic[cs] = ct
    return True

884. Decoded String at Index

An encoded string S is given. To find and write the decoded string to a tape, the encoded string is read one character at a time and the following steps are taken:

If the character read is a letter, that letter is written onto the tape. If the character read is a digit (say d), the entire current tape is repeatedly written d-1 more times in total. Now for some encoded string S, and an index K, find and return the K-th letter (1 indexed) in the decoded string.

Example 1:

Input: S = "leet2code3", K = 10 Output: "o"

The decoded string is guaranteed to have less than 2^63 letters

• Reduce K by K % word.len

• Count the total string size, use long

• if K == 0 && isLetter(char), return

• Corner case: "ab2", 4

public String decodeAtIndex(String S, int K) {
    // count the total string size
    long size = 0;
    for(char c: S.toCharArray()){
        if(Character.isDigit(c)) size *= c - '0';
        else size++;
    }

    // backtrack
    for(int i=S.length()-1; i>=0; i--){
        char c = S.charAt(i);
        K %= size;
        if(K == 0 && Character.isLetter(c)) return Character.toString(c);

        if(Character.isDigit(c)) size /= c -'0';
        else size--;
    }
    return "";
}

438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

def findAnagrams(self, s: str, p: str) -> List[int]:
    if len(p) > len(s): return []
    ans = []
    map_p = [0]*26
    map_s = [0]*26
    
    for i in range(len(p)):
        map_p[ord(p[i]) - ord('a')] += 1
        map_s[ord(s[i]) - ord('a')] += 1
    
    
    for i in range(0, len(s)-len(p)+1):
        if map_s == map_p: 
            ans.append(i)
        
        # 再下去 i + len(p) 會超過邊界
        if i == len(s)-len(p): break
        
        map_s[ord(s[i]) - ord('a')] -= 1
        map_s[ord(s[i+len(p)]) - ord('a')] += 1
        
    return ans

567 Permutation String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

• Put s1 and s2 into 2 maps

• A helper function to validate permutation

• Loop to update the map

• Time O(l1l2), Space O(226)

public boolean checkInclusion(String s1, String s2) {
    if(s2.length() < s1.length()) return false;
    int[] map1 = new int[26];
    int[] map2 = new int[26];

    for(int i=0; i<s1.length(); i++){
        map1[s1.charAt(i)-'a']++;
        map2[s2.charAt(i)-'a']++;
    }


    for(int i=s1.length(); i<s2.length(); i++){
        if(match(map1, map2)) return true;
        map2[s2.charAt(i)-'a']++;
        map2[s2.charAt(i-s1.length())-'a']--;
    }

    // if match 在最後面 ("ab", "....ab")
    return match(map1, map2);
}

private boolean match(int[] map1, int[] map2){
    for(int i=0; i<26; i++){
        if(map1[i] != map2[i]) return false;
    }
    return true;
}

316. Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

• Greedy + stack

• Only add char if it hasn't seen

• Discard the last char in stack if

  1. The current char is smaller

  2. We can seen it later in string

def removeDuplicateLetters(self, s: str) -> str:
    stack = []
    lastPosition = {c:i for i, c in enumerate(s)}
    seen = set()
    
    for i, c in enumerate(s):
        if c not in seen:
            while stack and c < stack[-1] and lastPosition[stack[-1]] > i:
                last = stack.pop()
                seen.remove(last)
            seen.add(c)
            stack.append(c)
            
    return ''.join(stack)