题目描述

同构字符串问题：

给定两个字符串 s 和 t，判断这两个字符串是否同构。所谓同构字符串，是指可以通过重新排列 s 中的字符来得到 t。两个字符串中所有字符都出现相同的次数，并且字符的相对顺序在 s 和 t 中保持一致。注意，这里的相对顺序指的是任意两个字符在字符串中的先后关系，而不一定是它们在字符串中的位置索引。

示例 1:

输入: s = "egg", t = "add"
输出: true
解释: 两个字符串都可以通过重新排列字符得到 "ead" 或者 "eda"。

示例 2:

输入: s = "foo", t = "bar"
输出: false

示例 3:

输入: s = "paper", t = "title"
输出: true

解题思路

一种直观的方法是使用哈希表来记录每个字符在 s 和 t 中出现的相对位置。由于要判断相对顺序，我们可以将字符映射到其首次出现的索引上，然后比较两个字符串在映射后的索引序列是否相同。

但是，这种方法需要确保索引映射的唯一性，并且处理可能存在的字符映射冲突。为了简化问题，我们可以使用一个数组（或哈希表）来记录 s 中每个字符到其首次出现索引的映射，同时遍历 t 时检查当前字符的映射索引是否与 s 中该字符的映射索引一致，并且检查是否已经存在相同的映射索引（处理重复字符的情况）。

PHP 代码示例

function isIsomorphic(string $s, string $t): bool {
    if (strlen($s) !== strlen($t)) {
        return false;
    }
    
    $mapS = [];
    $mapT = [];
    
    for ($i = 0; $i < strlen($s); $i++) {
        $charS = $s[$i];
        $charT = $t[$i];
        
        if (!isset($mapS[$charS])) {
            $mapS[$charS] = $i;
        }
        if (!isset($mapT[$charT])) {
            $mapT[$charT] = $i;
        }
        
        if ($mapS[$charS] !== $mapT[$charT]) {
            return false;
        }
    }
    
    return true;
}

// 测试
echo isIsomorphic("egg", "add") ? "true" : "false";  // true
echo isIsomorphic("foo", "bar") ? "true" : "false";  // false
echo isIsomorphic("paper", "title") ? "true" : "false";  // true

Python 代码示例

def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    map_s = {}
    map_t = {}
    
    for i, (char_s, char_t) in enumerate(zip(s, t)):
        if char_s not in map_s:
            map_s[char_s] = i
        if char_t not in map_t:
            map_t[char_t] = i
        
        if map_s[char_s] != map_t[char_t]:
            return False
    
    return True

# 测试
print(isIsomorphic("egg", "add"))  # True
print(isIsomorphic("foo", "bar"))  # False
print(isIsomorphic("paper", "title"))  # True

JavaScript 代码示例

function isIsomorphic(s, t) {
    if (s.length !== t.length) {
        return false;
    }
    
    const mapS = {};
    const mapT = {};
    
    for (let i = 0; i < s.length; i++) {
        const charS = s[i];
        const charT = t[i];
        
        if (!(charS in mapS)) {
            mapS[charS] = i;
        }
        if (!(charT in mapT)) {
            mapT[charT] = i;
        }
        
        if (mapS[charS] !== mapT[charT]) {
            return false;
        }
    }
    
    return true;
}

// 测试
console.log(isIsomorphic("egg", "add"));  // true
console.log(isIsomorphic("foo", "bar"));  // false
console.log(isIsomorphic("paper", "title"));  // true

在这些示例中，我们利用了哈希表（PHP的关联数组，Python和JavaScript的对象）来记录字符到索引的映射，并通过遍历和比较两个字符串来判断它们是否同构。希望这些示例能帮到你！