Leetcode # 859. Buddy Strings

https://leetcode.com/problems/buddy-strings

Solution

交換兩個 character 後 s 和 gaol 會一樣 ⇒ 回傳 True

1. s 和 goal 只有在 i, j 的兩個 character 不一樣 (s[i] != goal[i] and s[j] != goal [j])，
   且 s[i] = goal[j], s[j] = goal[i], i != j ⇒ 回傳 True
   1. len(s) != len(goal) ⇒ 回傳 False
   2. ∃ i, j s.t. s[i] != goal[i] and s[j] != goal[j] and s[i] == s[j] ⇒ 回傳 False
      例：”aa”, “bc”
   3. s 和 goal 不一樣的 character 多於兩個
   4. s[i] != goal[i] and s[j] != goal [j] 但 s[i] != goal[i]
2. s == goal, ∃ c ∈ [a-z] and s.count(c) >= 2 ⇒ 回傳 True
   例：”aa” → “aa“

Time Complexity: O(len(s))
Space Complexity: O(1) = O(26) (s and goal only consist of lowercase letters.)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def buddyStrings(self, s: str, goal: str) -> bool:
    if len(s) != len(goal): # Case 1-1: "a", "abc" - False
      return False
    diff = {}
    c_counter = collections.Counter()
    for i in range(len(s)):
      c_counter[s[i]] += 1
      if s[i] != goal[i]:
        if s[i] in diff: # Case 1-2: "aa", "bc" - False
          return False
        diff[s[i]] = goal[i]
        match len(diff):
          case 3: # Case 1-3: "abc", "cab" - False
            return False
          case 2:
            # Case 1-4: "ab", "bc" - False
            if goal[i] not in diff or diff[goal[i]] != s[i]:
              return False
    # Case 1: "abcba", "acbba" - True
    # Case 2: "aaa", "aaa" - True
    return len(diff) == 2 or \
           (len(diff) == 0 and \
            any(c_counter[c] >= 2 for c in c_counter))

Last Updated on 2023/08/16 by A1go