[LeetCode] 290. Word Pattern - 문제풀이

Description

영어소문자로 이루어진 패턴(pattern)과 주어진 공백으로 구분된 문자열(s)이 패턴에 맞게 일정하게 이루어져 있는지 여부를 판단하는 문제입니다.

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.

Solution 1. Map 활용

public boolean wordPattern(String pattern, String s) {

    //1. using map
    String[] words = s.split(" ");
    char[] patterns = pattern.toCharArray();
    if(words.length != patterns.length) {return false;}

    Map map = new HashMap<>();

    for (Integer i = 0; i < words.length; i++) {
        String word = words[i];
        Character p = patterns[i];
        if (map.put(p, i) != map.put(word, i)){   // pattern과 word로 각각 마지막 인덱스 저장 , 반환되는 이전 인덱스가 같지 않으면 다른 데이터가 들어간 것
            return false;
        }
    }
    return true;
}

Map을 활용하는 방법입니다. 주요 아이디어는 공백을 기준으로 split한 문자열(words[i]) 과 패턴(patterns[i])을 각각 키로하여 마지막 인덱스를 map에 저장합니다. 같은위치에서 put()메서드 호출시 반환되는 이전 index값이 다를 경우 false를 반환해 주면 됩니다.

Solution 2. Array 활용

public boolean wordPattern2(String pattern, String s) { 
    //2. using array
    String[] map = new String[26]; // 소문자 a-z 26char  > 00~25
    String[] words = s.split(" ");
    char[] patterns = pattern.toCharArray();
    if(words.length != patterns.length) {return false;}

    for (int i = 0; i < patterns.length; i++) {
        int mapIndex = pattern.charAt(i)-'a';  // [97~122]-a(97) = 0~25
        String str = words[i];
        String mapStr = map[mapIndex];

        if(mapStr == null){ // 최초 패턴 입력시
            //현재 배열에 같은값이 들어간적이 있으면 안됨.
            if(Arrays.stream(map).anyMatch(o->str.equals(o)))return false;
            map[mapIndex] = str;
        }else{ // 맵에 데이터가 있으면 현재 문자와 같아야함
            if(!mapStr.equals(str) ){
                return false;
            }
        }
    }
    return true;
}

패턴은 영어 소문자(a-z)까지 26자리로 이루어져있으므로 배열(String[26])을 사용하여 각 캐릭터에 맞는 인덱스에 마지막 문자열을 넣어 줍니다. 동일한 패턴에 다른 문자열이 들어가 있거나 맵에 문자를 넣을때 다른 패턴에 같은 문자가 들어가 있으면 false를 반환합니다.

Reference

Word Pattern - LeetCode