[Easy] LeetCode - no.290 Word Pattern : Java

https://leetcode.com/problems/word-pattern/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

String pattern과 s가 서로 일대일 대응(bijection) 관계에 있는지 여부를 판단

이 때 중복된 문자는 같은 단어에 대응해야 하고, 다른 문자는 다른 단어에 대응해야 함

두 문자가 같은 단어에 대응하거나, 두 단어가 같은 문자에 대응하면 안 됨

Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation:The bijection can be established as:'a' maps to "dog".'b' maps to "cat".

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

 

 

 

풀이1

import java.util.*;

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

        if (pattern.length() != arr.length) {
            return false;
        }
        
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String str = arr[i];

            if (!map.containsKey(c)) {
                if (!map.containsValue(str)) {
                    map.put(c, str);
                } else {
                    return false;
                }
            } else {
                if (!map.get(c).equals(str)) {
                    return false;
                }
            }
        }

        return true;
    }
}

• HashMap 사용
• pattern과 arr의 길이가 같지 않다면 false 반환
• map.containsKey()와 map.containsValue()를 사용
• 시간복잡도 : O(N^2)

💬 containsValue()를 활용했지만, 시간적인 효율성이 좋지 않음

 

 

 

풀이2

  public boolean wordPattern2(String pattern, String s) {
    String[] words = s.split(" ");

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

    HashMap<Character, String> charToWord = new HashMap<>();
    HashSet<String> seenWords = new HashSet<>();

    for (int i = 0; i < pattern.length(); i++) {
      char c = pattern.charAt(i);
      String w = words[i];

      if (charToWord.containsKey(c)) {
        if (!charToWord.get(c).equals(w)) {
          return false;
        }
      } else {
        if (seenWords.contains(w)) {
          return false;
        }

        charToWord.put(c, w);
        seenWords.add(w);
      }
    }

    return true;
  }

• HashMap과 HashSet 사용
• map 사용은 위와 비슷하지만, set에 이미 나왔던 단어들을 저장함으로써 containsValue()보다 빠르게 조회 가능
• 시간복잡도 : O(N)

💬 생각해보지 못한 풀이지만 한 번에 이해하기 쉽고, 시간 효율성이 좋음