205. Isomorphic Strings

Description

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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: s = "egg", t = "add"

Output: true

Example 2

Input: s = "foo", t = "bar"

Output: false

Example 3

Input: s = "paper", t = "title"

Output: true

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if(s.length() != t.length()) return false;
        
        Map<Character, Character> map = new HashMap();
        
        for(int i = 0; i < s.length(); i++) {
            char ch1 = s.charAt(i);
            char ch2 = t.charAt(i);
            
            if(map.containsKey(ch1)) {
                if(map.get(ch1) != ch2) return false;
            } else {
                map.put(ch1, ch2);
            }
        }
        
        Set<Character> values = new HashSet(map.values());
        if(values.size() == map.values().size()) {
            return true;
        }
        
        return false;
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if(s.length() != t.length()) return false;
        
        int[] map = new int[256];
        
        for(int i = s.length()-1; i >= 0; i--) {
            int p1 = (int) s.charAt(i);
            int p2 = (int) t.charAt(i);

            if(map[p1] != map[p2+128]) {
                return false;
            } else {
                map[p1] = i;
                map[p2+128] = i;
            }
        }
        
        return true;
    }
}

Follow up