844. Backspace String Compare - Easy

前往題目

想法

• 馬上就想到可以用stack，但這樣空間就是O(n + m)，時間也是O(n + m)，不過s和t的長度都很短，不會影響很大

思路(使用Stack)

1. 兩個stack存放s和t
2. 比較大小和彈出比較char
3. 都通過就是true

Code(使用Stack)

class Solution {
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> stackS = new Stack<>();
        Stack<Character> stackT = new Stack<>();
        
        // Building stacks
        for (char c : s.toCharArray()) {
            if (c != '#'){
                stackS.push(c);
            } else if (!stackS.isEmpty()){
                stackS.pop();
            }
        }

        for (char c : t.toCharArray()) {
            if (c != '#') {
                stackT.push(c);
            } else if (!stackT.isEmpty()){
                stackT.pop();
            }
        }

        // If the same, then stack size is the same
        if (stackS.size() != stackT.size()) return false;
        
        // Size will be changing while popping
        int size = stackS.size();

        for (int i = 0; i < size; ++i) {
            if (stackS.pop() != stackT.pop()) return false;
        }

        return true;
    }
}

Code(使用2 pointers)

使用這個方法，這個題目應該就不是Easy了🤣

# Helper function
def nextValidChar(str, index):
  backspace = 0
  while index >= 0:
    # Until skipped backspaced item
    if backspace == 0 and str[index] != "#":
      break
    elif str[index] == "#":
      backspace += 1
    else:
      backspace -= 1
    index -= 1
  return index

index_s, index_t = len(s) - 1, len(t) - 1
# Until char still exist
while index_s >= 0 or index_t >= 0:
  index_s = nextValidChar(s, index_s)
  index_t = nextValidChar(t, index_t)

  char_s = s[index_s] if index_s >= 0 else ""
  char_t = t[index_t] if index_t >= 0 else ""
  if char_s != char_t:
    return False
  index_s -= 1
  index_t -= 1

return True

2024/04/18

• 簡單的一題