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;
    }
}

1 comment:

  1. If you need your ex-girlfriend or ex-boyfriend to come crawling back to you on their knees (even if they're dating somebody else now) you have to watch this video
    right away...

    (VIDEO) Text Your Ex Back?

    ReplyDelete