[Leetcode Top Interview 150] 290. Word Pattern

난이도 : easy

문제링크

• 두개의 문자열이 주어진다 : pattern, s
• s가 pattern 문자열의 패턴을 따르는지 확인하라
• ex) pattern = "abba", s = "dog cat cat dog" => true
• ex) pattern = "abba", s = "dog cat cat fish" => false

 

1. 접근법

• 해시테이블 생성
  • pattern 문자에 대응되는 s 문자열
  • s 문자열에 대응되는 pattern 문자
• 한 문자씩 순회하면서,
  • 특정 pattern 문자에 대응되는 s 문자열이 해시테이블에서 가지고있는 값과 동등한지 확인
  • s 문자열에 대응되는 pattern 문자가 해시테이블에서 가지고있는 값과 동등한지 확인

 

3. 구현 코드

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

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

    Map<Character, String> pTos = new HashMap<>();
    Map<String, Character> sTop = new HashMap<>();

    for (int i = 0; i < pattern.length(); i++) {
        char p = pattern.charAt(i);
        if (pTos.containsKey(p)) {
            if (!pTos.get(p).equals(s1[i])) {
                return false;
            }
        } else {
            pTos.put(p, s1[i]);
        }

        String s_ = s1[i];
        if (sTop.containsKey(s_)) {
            if (!sTop.get(s_).equals(p)) {
                return false;
            }
        } else {
            sTop.put(s_, p);
        }
    }

    return true;
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 데이터를 순회함
• 공간복잡도 : O(n) - 모든 데이터를 생성해야 함