205. Isomorphic Strings
Tags:
Easy
Skills:
Hashmap
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu kiểm tra xem có thể ánh xạ từng ký tự trong chuỗi s sang một ký tự duy nhất trong chuỗi t và ngược lại, sao cho thứ tự các ký tự được bảo toàn và không có hai ký tự khác nhau trong s cùng ánh xạ đến một ký tự trong t
Hai chuỗi là isomorphic nếu bạn có thể thay thế từng ký tự trong chuỗi s bằng một ký tự duy nhất (theo một quy luật nhất định) để tạo thành chuỗi t
s phải ánh xạ duy nhất sang một ký tự trong t và không có hai ký tự khác nhau trong s cùng ánh xạ đến một ký tự trong t Giải thích ví dụ
true.false.true.Approach
s và t theo từng ký tựmapST : ánh xạ ký tự từ s->t mapTS : ánh xạ ký tự từ t->s false trueTime and space complexity
Solution
1function isIsomorphic(s: string, t: string): boolean {
2 if(s.length !== t.length) return false;
3
4 const mapST: Record<string, string> = {};
5 const mapTS: Record<string, string> = {};
6
7 for(let i =0; i < s.length; i++){
8 const char_s = s[i];
9 const char_t = t[i];
10
11 if((mapST[charS] && mapST[charT] !== charT) || (mapTS[charT] && mapTS[charT] !== charS)) {
12 return false;
13 }
14
15 mapST[charS] = charT;
16 mapTS[charT] = charS;
17 }
18
19 return true;
20};s phải luôn ánh xạ tới đúng một ký tự ở vị trí của t và ngược lạifalse Approach - 2
s và t s[i] và t[i] , nếu hai ký tự này đã từng xuất hiện ở các vị trí khác nhau trong hai chuỗi, thì hai chuỗi không isomorphicSolution - SC O(1)
1function isIsomorphic(s: string, t: string): boolean {
2 const last_seen_s = Array(128).fill(0);
3 const last_seen_t = Array(128).fill(0);
4
5 for (let i = 0; i < s.length; i++) {
6 const code_s = s.charCodeAt(i);
7 const code_t = t.charCodeAt(i);
8
9 if (last_seen_s[code_s] !== last_seen_t[code_t]) return false;
10
11 last_seen_s[code_s] = i + 1;
12 last_seen_t[code_t] = i + 1
13 }
14
15 return true;
16};i + 1 để tránh nhầm lẫn:Khi bạn gán last_seen_s[code_s] = i + 1 thì,
Như vậy, không bao giờ có sự nhầm lẫn giữa “chưa từng xuất hiện” và “xuất hiện ở vị trí 0”