925. 長按鍵入

• 思路
  • example
  • 雙指針
    • 一個字符串一個指針
    • 遍歷比較, 計數(shù)
  • 注意越界檢查，邊界情況
• 復雜度. 時間：O(m+n), 空間: O(1)

class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        i, j = 0, 0
        while i < len(name) and j < len(typed):
            cnt_name = 1
            ch = name[i]
            while i <= len(name) - 2 and name[i+1] == ch:
                cnt_name += 1
                i += 1
            i += 1 # now i == n-1, n, or ith is the new ch needs to be checked
            cnt_typed = 0
            while j < len(typed) and typed[j] == ch:
                cnt_typed += 1
                j += 1
            # jth is the new position
            if cnt_typed < cnt_name:
                return False 
        if i != len(name) or j != len(typed): # 有可能其中一個字符串有多余字符未比較
            return False   
        return True  

class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        m, n = len(name), len(typed) 
        i, j = 0, 0 
        while i < m and j < n:
            ch_name = name[i] 
            cnt_name = 0
            while i < m and name[i] == ch_name: # !!!
                i += 1
                cnt_name += 1 
            cnt_typed = 0 
            while j < n and typed[j] == ch_name: # !!!
                j += 1
                cnt_typed += 1
            if cnt_typed < cnt_name:
                return False 
        if i < m or j < n:
            return False 
        return True 

844. 比較含退格的字符串

• 思路
  • example
  • 雙棧比較

構(gòu)造去掉退格鍵的兩個字符串，然后比較

• 復雜度. 時間：O(m+n), 空間: O(m+n)

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        stack1, stack2 = [], []
        for i in range(len(s)):
            if s[i] == '#':
                if stack1:
                    stack1.pop() 
            else:
                stack1.append(s[i])
        for j in range(len(t)):
            if t[j] == '#':
                if stack2:
                    stack2.pop()  
            else:
                stack2.append(t[j])
        return stack1 == stack2  

• 進階：O(1) 空間復雜度
  • 從后向前 雙指針

*****ab#c
*****db#c
從后向前遍歷到倒數(shù)第4個字符時，兩個字符不相等，直接返回False
注意要處理連續(xù)#情形 （計數(shù)）

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j = len(s)-1, len(t)-1
        skip_s, skip_t = 0, 0  
        while i >= 0 or j >= 0: # 用or, s和t長度可能不同
            while i >= 0:
                if s[i] == '#':
                    skip_s += 1
                    i -= 1
                elif skip_s > 0:
                    skip_s -= 1
                    i -= 1 
                else: 
                    break  
            while j >= 0:
                if t[j] == '#':
                    skip_t += 1
                    j -= 1
                elif skip_t > 0:
                    skip_t -= 1
                    j -= 1
                else:
                    break  
            if i >= 0 and j >= 0:
                if s[i] != t[j]:
                    return False  
            elif i >= 0 or j >= 0: # 其中一個字符空了，另一個字符串還有剩余字符 
                return False  
            # 注意此時可能i==-1, j ==-1，下一步執(zhí)行后自然退出循環(huán)，返回True
            i -= 1
            j -= 1
        return True  

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        m, n = len(s), len(t) 
        i, j = m-1, n-1 
        skip_s, skip_t =0, 0 # !!!
        while i >= 0 or j >= 0: # !!!
            # 處理‘#’，找到當前可比較字符
            while i >= 0:
                if s[i] == '#':
                    i -= 1
                    skip_s += 1
                elif skip_s > 0:
                    i -= 1
                    skip_s -= 1
                else:
                    break 
            while j >= 0:
                if t[j] == '#':
                    j -= 1
                    skip_t += 1
                elif skip_t > 0:
                    j -= 1
                    skip_t -= 1
                else:
                    break 
            # 開始比較
            if i >= 0 and j >= 0: # !!!
                if s[i] != t[j]:
                    return False 
            elif i >= 0 or j >= 0: # !!!
                return False 
            i -= 1
            j -= 1
        return True # i = -1, j = -1