LeetCode 205 - Isomorphic Strings


Isomorphic Strings – Leetcode Java | Welkin Lan
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.

X. Normalize
https://blog.csdn.net/NoMasp/article/details/50611168
翻译完这题目就很自然的想到一个方法，我希望将字符串全部输出成数字序列：

For example,

Given "paper", return "01023".

Given "foo", return "011".

Given "isomorphic", return "0123245607".
  private ArrayList getArrayOrder(String str) {
    HashMap<Character, Integer> strM = new HashMap<>();
    int index = 0;
    ArrayList order = new ArrayList(str.length());
    for (int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);
      if (strM.containsKey(c)) {
        order.add(strM.get(c));
      } else {
        strM.put(c, index);
        order.add(index);
        index += 1;
      }
    }
    return order;
  }

  public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length())
      return false;
    ArrayList s0 = getArrayOrder(s), t0 = getArrayOrder(t);
    for (int i = 0; i < s0.size(); i++)
      if (s0.get(i) != t0.get(i))
        return false;
    return true;

  }

X.
https://leetcode.com/problems/isomorphic-strings/discuss/57802/Java-solution-using-HashMap
Check twice with helper method. O(n) time and O(n) space.
public boolean isIsomorphic(String s, String t) {
        if(s == null && t == null) return true;
        else if(s == null || t == null) return false;
        if(s.length() != t.length()) return false;
        return helper(s,t) && helper(t,s);
    }
    private boolean helper(String s, String t){
        Map<Character,Character> map = new HashMap<>();
        for(int i = 0;i<s.length();i++){
            if(!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i),t.charAt(i));
            }else{
                if(map.get(s.charAt(i)) != t.charAt(i) ) return false;
            }
        }
        return true;
    }

X.
https://segmentfault.com/a/1190000016865879
    public boolean isIsomorphic(String s, String t) {
        int[] stmap = new int[256];
        int[] tsmap = new int[256];
        Arrays.fill(stmap, -1);
        Arrays.fill(tsmap, -1);
        for (int i = 0; i < s.length(); i++) {
            if (stmap[s.charAt(i)] != tsmap[t.charAt(i)]) return false;
            stmap[s.charAt(i)] = i;
            tsmap[t.charAt(i)] = i;
        }
        return true;
    }

https://discuss.leetcode.com/topic/13001/short-java-solution-without-maps
The main idea is to store the last seen positions of current (i-th) characters in both strings. If previously stored positions are different then we know that the fact they're occuring in the current i-th position simultaneously is a mistake. We could use a map for storing but as we deal with chars which are basically ints and can be used as indices we can do the whole thing with an array.
    public boolean isIsomorphic(String s1, String s2) {
        int[] m = new int[512];
        for (int i = 0; i < s1.length(); i++) {
            if (m[s1.charAt(i)] != m[s2.charAt(i)+256]) return false;
            m[s1.charAt(i)] = m[s2.charAt(i)+256] = i+1;
        }
        return true;
    }
X. http://www.cnblogs.com/grandyang/p/4465779.html
根据一对一映射的特点，我们需要用两个哈希表分别来记录原字符串和目标字符串中字符出现情况，由于ASCII码只有256个字符，所以我们可以用一个256大小的数组来代替哈希表，并初始化为0，我们遍历原字符串，分别从源字符串和目标字符串取出一个字符，然后分别在两个哈希表中查找其值，若不相等，则返回false，若想等，将其值更新为i + 1
    bool isIsomorphic(string s, string t) {
        int m1[256] = {0}, m2[256] = {0}, n = s.size();
        for (int i = 0; i < n; ++i) {
            if (m1[s[i]] != m2[t[i]]) return false;
            m1[s[i]] = i + 1;
            m2[t[i]] = i + 1;
        }
        return true;
    }
X. 
We could use extra space – hashtable to save mapped values and check time is O(1)
https://segmentfault.com/a/1190000003709248
用一个哈希表记录字符串s中字母到字符串t中字母的映射关系，一个集合记录已经映射过的字母。或者用两个哈希表记录双向的映射关系。这里不能只用一个哈希表，因为要排除egg->ddd这种多对一的映射。

    public boolean isIsomorphic(String s, String t) {
        HashMap<Character,Character> map = new HashMap<>();
        HashSet<Character> mapped = new HashSet<>();
        for (int i=0; i<s.length(); i++){
            if (map.containsKey(s.charAt(i))){
                if (t.charAt(i)==map.get(s.charAt(i))) continue;
                else return false;
            }
            else if (mapped.contains(t.charAt(i))) return false;
            map.put(s.charAt(i),t.charAt(i));
            mapped.add(t.charAt(i));
        }
        return true;
    }
A:
A simple HashMap<s.char, t.char> question, only rule is that No two characters may map to the same character.
We could use map.containsValue() => O(n) time to check whether value is existed
http://www.programcreek.com/2014/05/leetcode-isomorphic-strings-java/
- Not efficient

    public boolean isIsomorphic(String s, String t) {
        HashMap<Character,Character> map = new HashMap<>();
        for (int i=0; i<s.length(); i++){
            if (map.containsKey(s.charAt(i))){
                if (t.charAt(i)==map.get(s.charAt(i))) continue;
                else return false;
            }
            else if (map.containsValue(t.charAt(i))) return false;
            map.put(s.charAt(i),t.charAt(i));
        }
        return true;
    }

https://sisijava.wordpress.com/2015/05/05/leetcode-isomorphic-strings/
    public boolean isIsomorphic(String s, String t) {
            if(s == null && t == null){
                return true;
            }
            else if(s == null ||t == null){
                return false;
            }
            else{
                if(s == t){
                    return true;
                }
                else{
                    if(s.length() != t.length()){
                        return false;
                    }
                    else{
                        int l = s.length();
                        HashMap<Character, Character> a = new HashMap<Character, Character>();
                        HashMap<Character, Character> b = new HashMap<Character, Character>();
                        for(int i = 0; i < l; i++){
                            char sc = s.charAt(i);
                            char tc = t.charAt(i);
                                if(!a.containsKey(tc) && !b.containsKey(sc)){
                                    a.put(tc, sc);
                                    b.put(sc, tc);
                                }
                                else{
                                    if(a.containsKey(tc) ? a.get(tc)!=sc : b.get(sc)!=tc) 
                                        return false;
                                }
                        }
                    }
                }
            }
            return true;
    }
X. http://www.cnblogs.com/easonliu/p/4465650.html
就是记录遍历s的每一个字母，并且记录s[i]到t[i]的映射，当发现与已有的映射不同时，说明无法同构，直接return false。但是这样只能保证从s到t的映射，不能保证从t到s的映射，所以交换s与t的位置再重来一遍上述的遍历就OK了。
     bool isIsomorphic(string s, string t) {
 4         if (s.length() != t.length()) return false;
 5         map<char, char> mp;
 6         for (int i = 0; i < s.length(); ++i) {
 7             if (mp.find(s[i]) == mp.end()) mp[s[i]] = t[i];
 8             else if (mp[s[i]] != t[i]) return false;
 9         }
10         mp.clear();
11         for (int i = 0; i < s.length(); ++i) {
12             if (mp.find(t[i]) == mp.end()) mp[t[i]] = s[i];
13             else if (mp[t[i]] != s[i]) return false;
14         }
15         return true;
16     }
http://www.cnblogs.com/zhuli19901106/p/4469153.html
 6     bool isIsomorphic(string s, string t) {
 7         return check(s, t) && check(t, s);
 8     }
 9 private:
10     bool check(string s, string t) {
11         char a[256];
12         
13         memset(a, 0, sizeof(a));
14         int i;
15         int n = s.length();
16         
17         for (i = 0; i < n; ++i) {
18             if (a[s[i]] == 0) {
19                 a[s[i]] = t[i];
20             }
21             s[i] = a[s[i]];
22         }
23         
24         return s == t;
25     }
http://www.zhuangjingyang.com/leetcode-isomorphic-strings/

X.
http://likesky3.iteye.com/blog/2237360
思路1：维护两个哈希表，char[] map, boolean[] used, 长度均为256，map[charS] = charT, 表示将字符charS 映射为charT, used[charT]==true 表示charT已经被某个字符映射过了。同步遍历字符串s & t,记两者当前的字符分别为charS, charT, 若charS是新字符，且charT没有被使用，则我们可将其同charT建立映射关系，否则说明有两个不同的字符试图映射到同一个字符上，不符合要求；若charS已被建立映射关系，则检查charT是否和charS的映射字符相等，不相等不符合题目要求的“All occurrences of a character must be replaced with another character ”。 
思路2：参考https://leetcode.com/discuss/33854/my-6-lines-solution，又是一个怎巧妙了得~ 这个思路也是用两个哈希表，不同于思路1直接将s中的字符映射到t中字符，它是将s 和 t中的字符同时映射到下标上，因为若个字符若存在映射关系，则必然是出现在相同的下标位置，实现中由于初始值为0，建立映射时使用 i + 1，以区分未映射状态和映射到下标为0的状态。 
  1.     // Method 2 https://leetcode.com/discuss/33854/my-6-lines-solution  
  2.     public boolean isIsomorphic(String s, String t) {  
  3.         int[] map1 = new int[256];  
  4.         int[] map2 = new int[256];  
  5.         for (int i = 0; i < s.length(); i++) {  
  6.             if (map1[s.charAt(i)] != map2[t.charAt(i)])  
  7.                 return false;  
  8.             map1[s.charAt(i)] = i + 1;  
  9.             map2[t.charAt(i)] = i + 1;  
  10.         }  
  11.         return true;  
  12.     }  
  13.     // Method 1  
  14.     public boolean isIsomorphic1(String s, String t) {  
  15.         if (s == null || t == null) return false;  
  16.         char[] map = new char[256];  
  17.         boolean[] used = new boolean[256];  
  18.         for (int i = 0; i < s.length(); i++) {  
  19.             char charS = s.charAt(i);  
  20.             char charT = t.charAt(i);  
  21.             if (map[charS] == 0) {  
  22.                 if (used[charT]) return false; // No two characters may map to the same character   
  23.                 map[charS] = charT;  
  24.                 used[charT] = true;  
  25.             } else if (map[charS] != charT){  
  26.                 return false; // All occurrences of a character must be replaced with another character   
  27.             }  
  28.         }  
  29.         return true;  
  30.     }  
https://leetcode.com/discuss/34174/my-simple-java-solution
public boolean isIsomorphic(String s, String t) { char[] map1 = new char[256], map2 = new char[256]; for (int i = 0; i < s.length(); i++) { char a = s.charAt(i); char b = t.charAt(i); if (!this.map(a, b, map1) || !this.map(b, a, map2)) { return false; } } return true; } private boolean map(char a, char b, char[] map) { if (map[a] == 0) { map[a] = b; } return map[a] == b; }
The problem is that a char in Java takes up two bytes. Since the inputs are not limited to ASCII strings in the question, you may have two char[65536] for this solution.
public boolean isIsomorphic(String s1, String s2) { int[] m = new int[512]; for (int i = 0; i < s1.length(); i++) { if (m[s1.charAt(i)] != m[s2.charAt(i)+256]) return false; m[s1.charAt(i)] = m[s2.charAt(i)+256] = i+1; } return true; }

public boolean isIsomorphic(String s, String t) { int[] map = new int[128]; int[] book = new int[128]; for (int i = 0; i < s.length(); i++) { int cs = (int) s.charAt(i); int ts = (int) t.charAt(i); if (map[cs] == 0 && book[ts] == 0) { map[cs] = ts; book[ts] = 1; } else if (map[cs] != ts) return false; } return true; }
https://leetcode.com/discuss/33854/my-6-lines-solution
bool isIsomorphic(string s, string t) { int m1[256] = {0}, m2[256] = {0}, n = s.size(); for (int i = 0; i < n; ++i) { if (m1[s[i]] != m2[t[i]]) return false; m1[s[i]] = i + 1; m2[t[i]] = i + 1; } return true; }
X. 在这里面我用了两个HashMap，一个HashMap用来记s的字符到t的映射，用于判断s中的两个字符不能用t中的同一个字符替换，另一个HashMap用来记t的字符到s的映射，用于判断t中的两个字符不能由s中同一个字符映射而来
http://my.oschina.net/Tsybius2014/blog/489587
    public boolean isIsomorphic(String s, String t) {
         
        if (s.length() != t.length()) {
            return false;
        }
        HashMap<Character, Character> hashMapS = new HashMap<Character, Character>();
        HashMap<Character, Character> hashMapT = new HashMap<Character, Character>();
         
        for (int i = 0; i < s.length(); i++) {
            if (hashMapS.containsKey(s.charAt(i))) {
                if (hashMapS.get(s.charAt(i)) != t.charAt(i)) {
                    return false;
                }
            } else {
                if (hashMapT.containsKey(t.charAt(i))) {
                    return false;
                }
                hashMapS.put(s.charAt(i), t.charAt(i));
                hashMapT.put(t.charAt(i), s.charAt(i));
            }
        }
         
        return true;
    }

}

    public boolean isIsomorphic(String s, String t) {
         
        if (s.length() != t.length()) {
            return false;
        }
        //虽然不考虑英文大小写，但因为不仅仅有26个英文字母，还可能有其他符号，所以数组要开得足够大
        int len = 40;  //这里数组长度开到40，可以满足题目AC
        char[] charInS = new char[len];
        char[] charInT = new char[len];
        for (int i = 0; i < len; i++) {
            charInS[i] = '0';
            charInT[i] = '0';
        }
         
        boolean bTrue;
        for (int i = 0; i < s.length(); i++) {
            bTrue = false;
            //在数组s中找到当前字符串s的字母，如果数组t中相同位置字母不一致，则字符串不同构
            for (int j = 0; j < len; j++) {
                if (charInS[j] == '0') {
                    break;
                } else if (charInS[j] == s.charAt(i)) {
                    if (charInT[j] != t.charAt(i)) {
                        return false;
                    }
                    bTrue = true;
                } 
            }
            if (!bTrue) {
                //在数组t中找到当前字符串t的字母，如果数组s中相同位置字母不一致，则字符串不同构
                for (int j = 0; j < len; j++) {
                    if (charInT[j] == '0') {
                        break;
                    } else if (charInT[j] == t.charAt(i)) {
                        return false;
                    } 
                }
                //记录新的组合
                for (int k = 0; k < len; k++) {
                    if (charInS[k] == '0') {
                        charInS[k] = s.charAt(k);
                        charInT[k] = t.charAt(k);
                        break;
                    }
                }
            }
        }
         
        return true;
    }
Read full article from Isomorphic Strings – Leetcode Java | Welkin Lan
at
Labels: , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts