当前位置: 面试刷题>> 字符同构 (经典算法题500道)


题目描述补充

题目:字符同构检测

给定两个字符串 s1s2,判断它们是否字符同构。两个字符串字符同构的条件是:

  • 两个字符串的长度必须相等。
  • 可以通过重新排列 s1 的字符顺序得到 s2,同时也可以通过重新排列 s2 的字符顺序得到 s1
  • 换句话说,两个字符串包含完全相同的字符集合(包括重复字符),且每个字符在两个字符串中出现的次数相同。

示例

  • 输入:s1 = "egg", s2 = "gee"

  • 输出:true

  • 解释:两个字符串长度相等,且都包含字符 'e' 和 'g',每个字符在两个字符串中都出现了两次。

  • 输入:s1 = "foo", s2 = "bar"

  • 输出:false

  • 解释:两个字符串包含的字符集合不同。

PHP 代码示例

function isIsomorphic(string $s1, string $s2): bool {
    if (strlen($s1) !== strlen($s2)) {
        return false;
    }

    $map = [];
    $reverseMap = [];

    for ($i = 0; $i < strlen($s1); $i++) {
        $char1 = $s1[$i];
        $char2 = $s2[$i];

        if (!isset($map[$char1]) && !isset($reverseMap[$char2])) {
            $map[$char1] = $char2;
            $reverseMap[$char2] = $char1;
        } elseif (($map[$char1] ?? null) !== $char2 || ($reverseMap[$char2] ?? null) !== $char1) {
            return false;
        }
    }

    return true;
}

// 测试
echo isIsomorphic("egg", "gee") ? "true" : "false"; // 输出 true
echo isIsomorphic("foo", "bar") ? "true" : "false"; // 输出 false

Python 代码示例

def isIsomorphic(s1: str, s2: str) -> bool:
    if len(s1) != len(s2):
        return False

    map_s1_to_s2 = {}
    map_s2_to_s1 = {}

    for char1, char2 in zip(s1, s2):
        if char1 not in map_s1_to_s2:
            if char2 in map_s2_to_s1.values():
                return False
            map_s1_to_s2[char1] = char2
            map_s2_to_s1[char2] = char1
        elif map_s1_to_s2[char1] != char2:
            return False

    return True

# 测试
print(isIsomorphic("egg", "gee"))  # 输出 True
print(isIsomorphic("foo", "bar"))  # 输出 False

JavaScript 代码示例

function isIsomorphic(s1, s2) {
    if (s1.length !== s2.length) {
        return false;
    }

    const mapS1ToS2 = {};
    const mapS2ToS1 = {};

    for (let i = 0; i < s1.length; i++) {
        const char1 = s1[i];
        const char2 = s2[i];

        if (!(char1 in mapS1ToS2)) {
            if (mapS2ToS1[char2] !== undefined) {
                return false;
            }
            mapS1ToS2[char1] = char2;
            mapS2ToS1[char2] = char1;
        } else if (mapS1ToS2[char1] !== char2) {
            return false;
        }
    }

    return true;
}

// 测试
console.log(isIsomorphic("egg", "gee")); // 输出 true
console.log(isIsomorphic("foo", "bar")); // 输出 false

码小课内容分享

码小课网站中有更多关于算法和数据结构的精彩内容,包括但不限于排序算法、搜索算法、动态规划、图论算法等。通过系统学习这些内容,你将能够提升编程能力,掌握解决复杂问题的技巧。欢迎访问码小课网站,与众多学习者一同成长!

推荐面试题