Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1153.html

1153. String Transforms Into Another String

Level

Hard

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.

Note:

  1. 1 <= str1.length == str2.length <= 10^4
  2. Both str1 and str2 contain only lowercase English letters.

Solution

First consider some base cases. If either str1 or str2 is null, return false. If str1 and str2 are the same, return true. Otherwise, if all lowercase letters occur in str2, return false since conversions will definitely cause duplicates in str1 and make it impossible to transform str1 into str2.

Then loop over str1 and for each letter, store the indices in str1. If there exists two indices such that the letters at the two indices in str1 are the same but the letters at the two indices in str2 are different, return false since it is impossible to convert two same letters into two different letters. If no such indices exist, return true.

  • class Solution {
    public boolean canConvert(String str1, String str2) {
        if (str1 == null || str2 == null || str1.length() != str2.length())
            return false;
        if (str1.equals(str2))
            return true;
        Set<Character> set = new HashSet<Character>();
        int length = str1.length();
        for (int i = 0; i < length; i++)
            set.add(str2.charAt(i));
        if (set.size() == 26)
            return false;
        Map<Character, List<Integer>> map = new HashMap<Character, List<Integer>>();
        for (int i = 0; i < length; i++) {
            char c = str1.charAt(i);
            List<Integer> list = map.getOrDefault(c, new ArrayList<Integer>());
            list.add(i);
            map.put(c, list);
        }
        for (char c = 'a'; c <= 'z'; c++) {
            List<Integer> list = map.getOrDefault(c, new ArrayList<Integer>());
            int size = list.size();
            for (int i = 1; i < size; i++) {
                int prevIndex = list.get(i - 1), currIndex = list.get(i);
                if (str2.charAt(prevIndex) != str2.charAt(currIndex))
                    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;
    }
};

  • 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


  • 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
}

All Problems

All Solutions