2023-08-14:用go语言写算法。给出两个长度相同的字符串 str1 和 str2 请你帮忙判断字符串 str1 能不能在

举报
福大大架构师每日一题 发表于 2023/08/14 19:48:49 2023/08/14
【摘要】 2023-08-14:用go语言写算法。给出两个长度相同的字符串 str1 和 str2,请你帮忙判断字符串 str1 能不能在 零次 或 多次 转化 后变成字符串 str2,每一次转化时,你可以将 str1 中出现的 所有 相同字母变成其他 任何 小写英文字母,只有在字符串 str1 能够通过上述方式顺利转化为字符串 str2 时才能返回 true 。输入:str1 = “aabcc”, ...

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

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。