1153. 字符串转化 🔒

题目描述

给出两个长度相同的字符串 str1 和 str2。请你帮忙判断字符串 str1 能不能在零次或多次转化后变成字符串 str2。

每一次转化时，你可以将 str1 中出现的所有相同字母变成其他任何小写英文字母。

只有在字符串 str1 能够通过上述方式顺利转化为字符串 str2 时才能返回 true 。

示例 1：

输入：str1 = "aabcc", str2 = "ccdee"
输出：true
解释：将 'c' 变成 'e'，然后把 'b' 变成 'd'，接着再把 'a' 变成 'c'。注意，转化的顺序也很重要。

示例 2：

输入：str1 = "leetcode", str2 = "codeleet"
输出：false
解释：我们没有办法能够把 str1 转化为 str2。

提示：

1 <= str1.length == str2.length <= 10⁴
str1 和 str2 中都只会出现小写英文字母

解法

方法一：哈希表

我们可以先判断 str1 和 str2 是否相等，若相等，直接返回 true。

然后我们统计 str2 中每个字母出现的次数，若出现的次数等于 $26$，说明 str2 包含了所有的小写字母，那么无论 str1 如何转换，都无法得到 str2，直接返回 false。

否则，我们用数组或哈希表 d 记录 str1 中每个字母转换后的字母。遍历字符串 str1 和 str2，若 str1 中的某个字母已经转换过，那么其转换后的字母必须与 str2 中对应位置的字母相同，否则返回 false。

遍历结束后，返回 true。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为字符串 str1 的长度，而 $C$ 为字符集大小，本题中 $C = 26$。

Python3JavaC++GoTypeScript

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

1153. 字符串转化 🔒

题目描述

解法

方法一：哈希表

评论