未分類

Isomorphic Strings

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example:

1
2
3
4
5
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.
提示 解題應用
HashTable HashMap

Default:

1
2
3
func isIsomorphic(s string, t string) bool {
}

解答思路:

這個最初在寫時會因為題意上的陷阱而讓你忽略了一些細節,乍看之下要的是字串的結構相同,很容易就會將兩個字串間的字母做連結,但重點在於真的是1對1的關係嗎?以egg與add來說,直接把”e與a”做連結,”g與d”做連結後存入hashMap之中都沒有問題,eggb與adda呢?這時多出了”b與a”做連結,結果當然是false,因為有兩個(含)以上的點與a做連結,但是egga與addb的結果卻是true,原本的”e與a”做連結且多出”a與b”做連結是沒有問題的,看起來不僅僅是1對1的關係,而是以”連結點”與”被連結點”的關係,也就是說a點可以當連結點與被連結點各一個,但是不能存在a同時為兩個其它點的連結點或a為其它兩個點的被連結點,只要能抓住這個訣竅就可以很順利的寫出想要的程式。

程式碼解說:

如上述所說,以兩個不同的hashmap來存放”連結點”(origin)及”被連結點”(reverse)與其它點的關係,接著在迴圈取出字母的同時分別確認兩個hashmap是否存在其字母的關係,如果不存在就分別在兩個hashmap建立其字母的關係(例:一個存放a→b,另一則b→a),如果存在就檢查目前該字母在hashmap中所對應到的關係,是否與另一字串中對應的字母相同,若不同就回傳false,直到全數檢查完畢才回傳true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var runeT rune
origin := make(map[rune]rune)
reverse := make(map[rune]rune)
for i, v := range s {
runeT = rune(t[i])
char, ok := origin[v]
_, exist := reverse[runeT]
if !ok && !exist {
origin[v] = runeT
reverse[runeT] = v
continue
} else if char != runeT {
return false
}
}
return true

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func isIsomorphic(s string, t string) bool {
var runeT rune
origin := make(map[rune]rune)
reverse := make(map[rune]rune)
for i, v := range s {
runeT = rune(t[i])
char, ok := origin[v]
_, exist := reverse[runeT]
if !ok && !exist {
origin[v] = runeT
reverse[runeT] = v
continue
} else if char != runeT {
return false
}
}
return true
}

總結:

要判斷兩字串結構上是否相同,首先要注意的是字串的字母間關係是否為1對1的關係或是”連結點”與”被連結點”的關係以點a到點b來說,若為前者是絕對關係,a→b,b→a要放入相同的hashmap中,若為後者則是存在a點或b點可以當連結點與被連結點各一個,且不存在同時為兩個其它點的連結點或被連結點,a→b放入一hashmap而b→a放入另一hashmap以區別。

分享到