未分類

Isomorphic Strings

Go, HashTable, LeetCode

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以區別。

分享到