同构字符串


同构字符串

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定两个字符串 s 和 t,判断它们是否是同构的
如果 s 中的字符可以按某种映射关系替换得到 t,那么这两个字符串是同构的
每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序
不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。

示例 1:
输入:s = "egg", t = "add"
输出:true

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

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

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
思路:
首先字符串长度得相同,然后遍历字符串,将两个字符串的每个字符串作为key和value存储在map中,
如果出现map的key对应的value和另一个字符串中对应的字符不同,返回false,
如果出现第二个字符串中的字符已经存在map的value中,且第一个字符串中的key不存在,返回false

代码:
/**
* @param String $s
* @param String $t
*
* @return Boolean
*/
function isIsomorphic($s, $t)
{
// 长度不同返回false
if (strlen($s) !== strlen($t)) {
return false;
}

$map = [];

for ($i = 0; $i < strlen($s); $i++) {
if (!isset($map[$s[$i]])) {
// 在key在map中不存在,并且值在map中存在,说明有其他key对应了这个value,返回false
if (in_array($t[$i], $map)) {
return false;
}

// 不存在map中,存储
$map[$s[$i]] = $t[$i];
} else {
// key对应的value和当前字符不同,说明key对应了多个value,返回false
if ($map[$s[$i]] != $t[$i]) {
return false;
}
}
}

return true;
}