Question

1153. String Transforms Into Another String

中文文档

Description

Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more _conversions_.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Return true if and only if you can transform str1 into str2.

 

Example 1:

Input: str1 = "aabcc", str2 = "ccdee"
Output: true
Explanation: Convert 'c' to 'e' then 'b' to 'd' then 'a' to 'c'. Note that the order of conversions matter.

Example 2:

Input: str1 = "leetcode", str2 = "codeleet"
Output: false
Explanation: There is no way to transform str1 to str2.

 

Constraints:

• 1 <= str1.length == str2.length <= 104
• str1 and str2 contain only lowercase English letters.

Solutions

Solution 1: Hash Table

First, we can check if str1 and str2 are equal. If they are, return true directly.

Then we count the occurrence of each letter in str2. If the occurrence equals $26$, it means str2 contains all lowercase letters. In this case, no matter how str1 is transformed, it cannot become str2, so return false directly.

Otherwise, we use an array or hash table d to record the letter each letter in str1 is transformed to. We traverse the strings str1 and str2. If a letter in str1 has been transformed, the transformed letter must be the same as the corresponding letter in str2, otherwise return false.

After the traversal, return true.

The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the length of the string str1, and $C$ is the size of the character set. In this problem, $C = 26$.

class Solution:
  def canConvert(self, str1: str, str2: str) -> bool:
    if str1 == str2:
      return True
    if len(set(str2)) == 26:
      return False
    d = {}
    for a, b in zip(str1, str2):
      if a not in d:
        d[a] = b
      elif d[a] != b:
        return False
    return True

class Solution {
  public boolean canConvert(String str1, String str2) {
    if (str1.equals(str2)) {
      return true;
    }
    int m = 0;
    int[] cnt = new int[26];
    int n = str1.length();
    for (int i = 0; i < n; ++i) {
      if (++cnt[str2.charAt(i) - 'a'] == 1) {
        ++m;
      }
    }
    if (m == 26) {
      return false;
    }
    int[] d = new int[26];
    for (int i = 0; i < n; ++i) {
      int a = str1.charAt(i) - 'a';
      int b = str2.charAt(i) - 'a';
      if (d[a] == 0) {
        d[a] = b + 1;
      } else if (d[a] != b + 1) {
        return false;
      }
    }
    return true;
  }
}

class Solution {
public:
  bool canConvert(string str1, string str2) {
    if (str1 == str2) {
      return true;
    }
    int cnt[26]{};
    int m = 0;
    for (char& c : str2) {
      if (++cnt[c - 'a'] == 1) {
        ++m;
      }
    }
    if (m == 26) {
      return false;
    }
    int d[26]{};
    for (int i = 0; i < str1.size(); ++i) {
      int a = str1[i] - 'a';
      int b = str2[i] - 'a';
      if (d[a] == 0) {
        d[a] = b + 1;
      } else if (d[a] != b + 1) {
        return false;
      }
    }
    return true;
  }
};

func canConvert(str1 string, str2 string) bool {
  if str1 == str2 {
    return true
  }
  s := map[rune]bool{}
  for _, c := range str2 {
    s[c] = true
    if len(s) == 26 {
      return false
    }
  }
  d := [26]int{}
  for i, c := range str1 {
    a, b := int(c-'a'), int(str2[i]-'a')
    if d[a] == 0 {
      d[a] = b + 1
    } else if d[a] != b+1 {
      return false
    }
  }
  return true
}

function canConvert(str1: string, str2: string): boolean {
  if (str1 === str2) {
    return true;
  }
  if (new Set(str2).size === 26) {
    return false;
  }
  const d: Map<string, string> = new Map();
  for (const [i, c] of str1.split('').entries()) {
    if (!d.has(c)) {
      d.set(c, str2[i]);
    } else if (d.get(c) !== str2[i]) {
      return false;
    }
  }
  return true;
}