Skip to content

1153. String Transforms Into Another String

  • Time: $O(n)$
  • Space: $O(26) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  bool canConvert(string str1, string str2) {
    if (str1 == str2)
      return true;

    vector<int> mappings(128);

    for (int i = 0; i < str1.length(); ++i) {
      const int a = str1[i];
      const int b = str2[i];
      if (mappings[a] != 0 && mappings[a] != b)
        return false;
      mappings[a] = b;
    }

    // No letter in the str1 maps to > 1 letter in the str2 and there is at
    // lest one temporary letter can break any loops.
    return unordered_set<char>(str2.begin(), str2.end()).size() < 26;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public boolean canConvert(String str1, String str2) {
    if (str1.equals(str2))
      return true;

    Map<Character, Character> mappings = new HashMap<>();

    for (int i = 0; i < str1.length(); ++i) {
      final char a = str1.charAt(i);
      final char b = str2.charAt(i);
      if (mappings.getOrDefault(a, b) != b)
        return false;
      mappings.put(a, b);
    }

    // No letter in the str1 maps to > 1 letter in the str2 and there is at
    // lest one temporary letter can break any loops.
    return new HashSet<>(mappings.values()).size() < 26;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def canConvert(self, str1: str, str2: str) -> bool:
    if str1 == str2:
      return True

    mappings = {}

    for a, b in zip(str1, str2):
      if mappings.get(a, b) != b:
        return False
      mappings[a] = b

    # No letter in the str1 maps to > 1 letter in the str2 and there is at
    # lest one temporary letter can break any loops.
    return len(set(str2)) < 26