2023-08-14：用go语言写算法。给出两个长度相同的字符串 str1 和 str2，

请你帮忙判断字符串 str1 能不能在 零次 或 多次 转化 后变成字符串 str2，

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

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

输入：str1 = “aabcc”, str2 = “ccdee”。

输出：true。

来自谷歌、亚马逊、微软、蔚来、腾讯、字节跳动、Uber。

来自左程云。

答案2023-08-14：

大体过程如下：

1.首先，比较两个字符串 str1 和 str2 是否相等。如果相等，则可以直接返回 true，因为不需要进行转化操作。

2.创建一个长度为 26 的整数数组 mapChars，用于记录字符串 str2 中每个字母的出现次数。

3.创建一个变量 kinds，用于记录字符串 str2 中不同字母的种类数量。

4.遍历字符串 str2，对于每个字符 ch，将其转换为对应的索引 idx。如果 mapChars[idx] 的值为 0，说明该字符还没有出现过，将 kinds 值增加 1，并且将 mapChars[idx] 的值加 1。

5.如果 kinds 的值已经达到 26（字母表中的所有字母种类数量），则说明字符串 str2 中的所有字母都已经出现过，无法再进行转化操作，直接返回 false。

6.将 mapChars 数组中的所有元素重置为 -1。

7.遍历字符串 str1，对于每个字符 ch，将其转换为对应的索引 cur。

8.如果 mapChars[cur] 不等于 -1，并且 str2[mapChars[cur]] 不等于 str2[i]，则说明已经对字符 ch 进行了转化，但转化后的字符与 str2 中对应位置的字符不相等，直接返回 false。

9.将 mapChars[cur] 的值更新为当前索引 i。

10.如果成功遍历完整个字符串 str1，则说明 str1 可以通过零次或多次转化变成字符串 str2，返回 true。

总的时间复杂度：假设字符串的长度为 n，遍历 str2 的时间复杂度是 O(n)，遍历 str1 的时间复杂度也是 O(n)，因此总的时间复杂度为 O(n)。

总的空间复杂度：除了字符串 str1 和 str2 的空间占用，还创建了长度为 26 的整数数组 mapChars，因此总的空间复杂度为 O(1)。

go语言完整代码如下：

package main

import (
    "fmt"
)

func canConvert(str1 string, str2 string) bool {
    if str1 == str2 {
        return true
    }

    mapChars := make([]int, 26)
    kinds := 0

    for _, ch := range str2 {
        idx := ch - 'a'
        if mapChars[idx] == 0 {
            kinds++
        }
        mapChars[idx]++
    }

    if kinds == 26 {
        return false
    }

    for i := range mapChars {
        mapChars[i] = -1
    }

    for i, ch := range str1 {
        cur := ch - 'a'
        if mapChars[cur] != -1 && str2[mapChars[cur]] != str2[i] {
            return false
        }
        mapChars[cur] = i
    }

    return true
}

func main() {
    str1 := "aabcc"
    str2 := "ccdee"
    result := canConvert(str1, str2)
    fmt.Println(result)
}

c++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canConvert(string str1, string str2) {
    if (str1 == str2) {
        return true;
    }

    vector<int> map(26, 0);
    int kinds = 0;

    for (int i = 0; i < str2.length(); i++) {
        if (map[str2[i] - 'a']++ == 0) {
            kinds++;
        }
    }

    if (kinds == 26) {
        return false;
    }

    fill(map.begin(), map.end(), -1);

    for (int i = 0; i < str1.length(); i++) {
        int cur = str1[i] - 'a';
        if (map[cur] != -1 && str2[map[cur]] != str2[i]) {
            return false;
        }
        map[cur] = i;
    }

    return true;
}

int main() {
    string str1 = "aabcc";
    string str2 = "ccdee";
    bool result = canConvert(str1, str2);
    cout << boolalpha << result << endl;
    return 0;
}

c语言完整代码如下：

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool canConvert(const char* str1, const char* str2) {
    if (strcmp(str1, str2) == 0) {
        return true;
    }

    int map[26] = { 0 };
    int kinds = 0;

    for (int i = 0; i < strlen(str2); i++) {
        if (map[str2[i] - 'a']++ == 0) {
            kinds++;
        }
    }

    if (kinds == 26) {
        return false;
    }

    memset(map, -1, sizeof(map));

    for (int i = 0; i < strlen(str1); i++) {
        int cur = str1[i] - 'a';

        if (map[cur] != -1 && str2[map[cur]] != str2[i]) {
            return false;
        }

        map[cur] = i;
    }

    return true;
}

int main() {
    const char* str1 = "aabcc";
    const char* str2 = "ccdee";
    bool result = canConvert(str1, str2);

    printf("%s\n", result ? "true" : "false");

    return 0;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接