[leetcode #290] Word Pattern

Problem

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.

Idea

brute-force로 풀 수 있기 때문에 쉬운 난이도인 문제다.

우선 주어진 String s를 ' '로 split한 뒤 pattern의 길이와 비교한다. 길이가 다를 경우 패턴이 다르므로 곧바로 false를 리턴한다.

이후 pattern의 문자를 하나씩 탐색하면서 split된 문자열도 함게 탐색한다. 맵의 key에 해당 문자가 없고, split된 문자열이 value에도 없을 경우 map에 문자와 문자열의 쌍을 넣는다. 만약 이미 split된 문자열이 value에 존재한다면 이미 다른 문자와 매칭되어 있다는 뜻이므로 false를 리턴한다.

key에 문자가 들어가 있는데 매칭된 문자열이 split된 문자열이랑 다를 경우에도 false를 리턴한다.

전체 pattern을 다 탐색했을 경우 true를 리턴하면 된다.

Solution

class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<Character, String> map = new HashMap<>();
        String[] splitted = s.split(" ");

        if (pattern.length() != splitted.length) {
            return false;
        }

        for (int i=0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (!map.containsKey(c)) {
                if (map.containsValue(splitted[i])) {
                    return false;
                }
                map.put(c, splitted[i]);
                continue;
            }
            if (!splitted[i].equals(map.get(c))) {
                return false;
            }
        }

        return true;
    }
}

Reference

https://leetcode.com/problems/word-pattern/