[LeetCode/Top Interview 150] [Hash Table] 290. Word Pattern

문제 링크: https://leetcode.com/problems/word-pattern/description/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

Constraints:

1 <= pattern.length <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lowercase English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

전략:

패턴과 문장의 공백이 아닌 단어들이 일대일로 매칭(전단사 함수) 되어야 한다.
문장 s는 영문 소문자와 공백 ' '만으로 이루어져 있다.
문장 s는 공백으로 시작하거나 끝나지 않는다.(trim 할 필요 없음)
문장 s의 단어들은 모두 공백 1칸으로 구분지어진다.

패턴의 알파벳 1개당 1개의 단어를 할당해 그 위치에 맞는 단어가 나오는지 체크
알파벳과 단어가 서로 1:1 연관이어야 한다

char[]과 HashMap으로 알파벳->단어와 단어->알파벳 관계를 각각 보증하고, 기존에 저장된 값과 하나라도 다르다면 즉시 false 리턴.

코드 구현:

import java.util.StringTokenizer;

class Solution {
    public boolean wordPattern(String pattern, String s) {
        // 패턴과 문장의 공백이 아닌 단어들이 일대일로 매칭(전단사 함수) 되어야 한다.
        // 문장 s는 영문 소문자와 공백 ' '만으로 이루어져 있다.
        // 문장 s는 공백으로 시작하거나 끝나지 않는다.(trim 할 필요 없음)
        // 문장 s의 단어들은 모두 공백 1칸으로 구분지어진다.

        // 패턴의 알파벳 1개당 1개의 단어를 할당해 그 위치에 맞는 단어가 나오는지 체크
        // 알파벳과 단어가 서로 1:1 연관이어야 한다

        StringTokenizer st = new StringTokenizer(s, " ");
        HashMap<String, Character> map = new HashMap<String, Character>();
        if (st.countTokens() != pattern.length()) return false; // 갯수가 다르면 즉시 false

        String[] words = new String[pattern.length()]; // 입력받은 단어들
        String[] alphaWord = new String[26];
        
        for (int i=0;i<words.length;i++) {
            words[i] = st.nextToken();
            if (alphaWord[pattern.charAt(i)-'a'] == null) {                
                alphaWord[pattern.charAt(i)-'a'] = words[i];
            }
            if (words[i].equals(alphaWord[pattern.charAt(i)-'a']) && map.getOrDefault(words[i], pattern.charAt(i)) == pattern.charAt(i)) {
                // 알파벳 1글자가 하나의 단어만을 가리키는지 체크
                // 한 단어가 알파벳 한 글자만을 가리키는지 체크해야함
                alphaWord[pattern.charAt(i)-'a'] = words[i];
                map.put(words[i],pattern.charAt(i));
            } else {
                return false;
            }            
        }
        return true;
    }
}

실행결과:
Time: 0 ms (100.00%), Space: 39.71MB (99.89%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0290-word-pattern/0290-word-pattern.java

개선 방안:

성능상 충분히 좋은 것 같다. 굳이 꼽자면 StringTokenizer를 import 하지 않고 구현해보기?

Solutions 탭의 타인 코드:

class Solution {
public boolean wordPattern(String pattern, String str) {
    String[] words = str.split(" ");
    if (words.length != pattern.length())
        return false;
    Map index = new HashMap();
    for (Integer i=0; i<words.length; ++i) {
    // i를 int 가 아니라 Integer로 선언해서
    // 오토박싱 되서 Map에 넣어지는 타입과 동일하므로 !=로 비교 가능
    
    // HashMap의 타입 파라미터를 지정하지 않았으므로, String과 char 모두 키가 될 수 있다.
    // <키, 인덱스> 형식으로 값을 넣고, 한 값은 이미 HashMap에 존재하지만, 다른 값은 존재하지 않거나,
    // 둘 다 존재하더라도 서로 다른 인덱스를 가리키는 경우 false 리턴
    // 이미 같은 값이 둘 다 존재하면 둘 다 덮어쓰고 넘어간다.
        if (index.put(pattern.charAt(i), i) != index.put(words[i], i)) return false;
    }
    return true;
}
}
Time: 1 ms (73.53%), Space: 40 MB (98.52%) - LeetHub

회고:

진짜 잘하는 사람들의 코드는 상상이상이 될 수 있는 거 같다. Map사용시 타입을 지정해서 써야 한다는 고정관념에 사로잡혀 있었던 것 같다.
의외로 성능은 크게 차이나지 않았던 것은 내 코드에서도 길이 26짜리 배열이라는 상대적으로 작은 비용을 사용한 것이 원인이라고 생각된다.