Sunday, August 30, 2015

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,
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.
Understand the problem:
The problem is a little bit hard to understand. The essence of the problem is given two strings s and t. We replace the characters in t and is able to get back the string s. Note that the mapping relationship must be 1:1 matching. e.g. 
"foo, bar" => false, because o->a and o->r, which is one to many mapping.
"bar", "foo" => false, because a->o and r->o, which is many to one mapping. 

The idea is to maintain two hash maps. One store the normal mapping between s=>t, and the other map maintains the inverse mapping from t => s. For each character, we check both maps contains the s or t. 

Code (Java):
public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null || s.length() == 0) {
            return t == null || t.length() == 0;
        }
        
        if (t == null || t.length() == 0) {
            return s == null || s.length() == 0;
        }
        
        if (s.length() != t.length()) {
            return false;
        }
        
        Map<Character, Character> map = new HashMap<Character, Character>();
        Map<Character, Character> inverseMap = new HashMap<Character, Character>();
        
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            
            if (map.containsKey(sChar) && (tChar != map.get(sChar))) {
                return false;
            }
            
            if (inverseMap.containsKey(tChar) && (sChar != inverseMap.get(tChar))) {
                return false;
            }
            
            map.put(sChar, tChar);
            inverseMap.put(tChar, sChar);
        }
        
        return true;
    }
}

Update on 1/28/16:
public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if ((s == null || s.length() == 0) && (t == null || t.length() == 0)) {
            return true;
        }
        
        if ((s == null || s.length() == 0) || (t == null || t.length() == 0)) {
            return false;
        }
        
        if (s.length() != t.length()) {
            return false;
        }
        
        Map<Character, Character> forwardMap = new HashMap<>();
        Map<Character, Character> backwardMap = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            
            // Must not contain both
            if (!forwardMap.containsKey(sChar) && !backwardMap.containsKey(tChar)) {
                forwardMap.put(sChar, tChar);
                backwardMap.put(tChar, sChar);
            }
            
            // Only one contains
            if (!forwardMap.containsKey(sChar) || !backwardMap.containsKey(tChar)) {
                return false;
            }
            
            if (forwardMap.get(sChar) != tChar || backwardMap.get(tChar) != sChar) {
                return false;
            }
        }
        
        return true;
    }
}

No comments:

Post a Comment