Leetcode Isomorphic Strings solution Java
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.
Analysis
We can use a HashTable to map the letter from String1 to String2.
Let c1, c2 denote the current letter from string1 and string2 respectively.
If c1 is already in the table, and the letter mapped by c1 does not equal to c2, return false.
if c1 is not in the table, we need to check whether c2 has already been mapped or not.
To make this check faster, we can use another Table map the letter from c2 to c1.
Java Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
public boolean isIsomorphic(String s, String t) { if(s==null||t==null) return false; if(s.length()!=t.length()) return false; Map<Character, Character> map = new HashMap<>(); Map<Character, Character> map2 = new HashMap(); for(int i=0; i<s.length(); i++){ char c1 = s.charAt(i); char c2 = t.charAt(i); if(map.containsKey(c1)){ if(map.get(c1) != c2) return false; }else{ if(map2.containsKey(c2)) {//if c2 is already being mapped if(map2.get(c2) != c1) { return false; } } map.put(c1, c2); map2.put(c2, c1); } } return true; } |
