Leetcode - 205. Isomorphic Strings

 

[Must do Easy Question]

How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss

Isomorphic Strings - LeetCode

---

문제

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.

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

Note:
You may assume both s and t have the same length.

---

isomorphic 한지 판단하는 문제이다.

 

HashMap을 써서 s의 글자는 key에 t의 글자는 value에 넣어 같은 s의 같은 글자에 t의 같은 글자가 오는지 확인하는 방식으로 풀었다.

 

import java.util.*;
class Solution {
    HashMap<Character,Character> map = new HashMap();
    public boolean isIsomorphic(String s, String t) {
        int len = s.length(); // suppose s and t length is same
        for(int i = 0 ; i < len ; i++){
            char sc = s.charAt(i);
            char tc = t.charAt(i);
            if(i == 0){
                map.put(sc,tc);
            }else{
                if(map.containsKey(sc)){
                    //s 에서 이미 나온 글자라면 지금 t와 비교
                    if(map.get(sc) != tc){
                        return false;
                    }
                }//end of if
            }//end of else
            
        }//end of loop
        return true;
    }
}

 

1트 틀렸다.

ab 와 aa 를 true 라고 반환한다. 멍청한 내 코드 같으니라구

 

b는 map 에 없으니까 return false 의 조건에 들어가지 않는다.

 

t에서 같은게 나왔을때 s가 같은지도 확인하는 조건을 추가한다.

 

import java.util.*;
class Solution {
    HashMap<Character,Character> map = new HashMap();
    public boolean isIsomorphic(String s, String t) {
        int len = s.length(); // suppose s and t length is same
        for(int i = 0 ; i < len ; i++){
            char sc = s.charAt(i);
            char tc = t.charAt(i);
            if(i == 0){
                map.put(sc,tc);
            }else{
                if(map.containsKey(sc)){
                    //s 에서 이미 나온 글자라면 지금 t와 비교
                    if(map.get(sc) != tc){
                        return false;
                    }
                }//end of if
                //s에서 나오지 않은 글자인데 예를들어 ab aa 일때 b를 비교하는 경우
                //egg add 의 경우 e a // g d
                else if(map.containsValue(tc)){
                    //s는 새로운게 나왔는데 t에 기존에 있던게 있으면 안되지 
                    return false;
                }
            }//end of else
            map.put(sc,tc);
        }//end of loop
        return true;
    }
}

통과

Success

Details 

Runtime: 8 ms, faster than 43.44% of Java online submissions for Isomorphic Strings.

Memory Usage: 39.5 MB, less than 6.14% of Java online submissions for Isomorphic Strings.

 

그치만

느려,,

Hashmap 을 array 2개로 바꾸면 빨라진다는 소문이 들린다.

 

https://leetcode.com/problems/isomorphic-strings/discuss/57807/Java-3ms-beats-99.25

Java 3ms beats 99.25% - LeetCode Discuss

public class Solution {
    
    public boolean isIsomorphic(String sString, String tString) {

        char[] s = sString.toCharArray();
        char[] t = tString.toCharArray();

        int length = s.length;
        if(length != t.length) return false;
		//ASCII 문자 256을 담을 수 있는 char array
        char[] sm = new char[256];
        char[] tm = new char[256];
		
        for(int i=0; i<length; i++){
            char sc = s[i];
            char tc = t[i];
            if(sm[sc] == 0 && tm[tc] == 0){
            	//없는 문자라면 문자 ASCII 번호를 index 로 하는 배열에 char 을 저장
                sm[sc] = tc;
                tm[tc] = sc;
            }else{
            	//있는 문자라면
                if(sm[sc] != tc || tm[tc] != sc){
                	//s와 t 서로 다른 대응되는 문자가 있을 경우
                    return false;
                }
            }
        }
        return true;
    }
}

이분 코드를 보면 ASCII 문자와 HashMap 을 array 두개로 처리한 것을 볼 수 있다.

 

Success

Details 

Runtime: 1 ms, faster than 100.00% of Java online submissions for Isomorphic Strings.

Memory Usage: 38.9 MB, less than 26.32% of Java online submissions for Isomorphic Strings.

 

확실히 빠르다.

 

끗