当前位置： 面试刷题>> 同构字符串(经典算法150题)
### 题目描述
**同构字符串问题**：
给定两个字符串 `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 代码示例
```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 代码示例
```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 代码示例
```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的对象）来记录字符到索引的映射，并通过遍历和比较两个字符串来判断它们是否同构。希望这些示例能帮到你！