[LeetCode] 205. Isomorphic Strings

轉自LeetCode

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,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

<Solution>
由題意知道這是一對一的映射，所以可以用兩個 hash table 的來做比對

x 是 char，而 f(x) 是 index + 1

為什麼 f(x) 不用計數就好，例如 a 出現過幾次，對應的 b 也要出現幾次

這是因為除了字元是一對一映射之外，對應的字元也必須出現在相同位置

用 "aba" 和 "baa" 為例

a -> b，b -> a

a 都是出現兩次，b 都是出現一次

如果沒有考慮到位置的因素，會判斷錯誤

那至於為什麼是 index + 1，因為把 0 拿來當初始值用了

code 如下

C++

	class Solution {
	public:
	bool isIsomorphic(string s, string t) {
	//> ASCII at most 256 characters
	int hash_1[256] = {0}, hash_2[256] = {0};
	const int size = s.length();
	for(int i = 0; i < size; i++) {
	if(hash_1[s[i]] != hash_2[t[i]]) {
	return false;
	}
	hash_1[s[i]] = i + 1;
	hash_2[t[i]] = i + 1;
	}
	return true;
	}
	};

view raw isomorphicString.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public boolean isIsomorphic(String s, String t) {
	if(s == null) {
	return true;
	}
	final int len = s.length();
	int[] table_1 = new int[256];
	int[] table_2 = new int[256];
	for(int i = 0; i < len; ++i) {
	if(table_1[s.charAt(i)] != table_2[t.charAt(i)]) {
	return false;
	}
	table_1[s.charAt(i)] = i+1;
	table_2[t.charAt(i)] = i+1;
	}
	return true;
	}
	}

view raw isomorphicString.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun isIsomorphic(s: String, t: String): Boolean {
	val table1 = mutableMapOf<Char,Int>()
	val table2 = mutableMapOf<Char,Int>()
	for(i in s.indices) {
	if(table1[s[i]] != table2[t[i]]) {
	return false
	}
	table1[s[i]] = i
	table2[t[i]] = i
	}
	return true
	}
	}

view raw isomorphic_strings.kt hosted with ❤ by GitHub