290. Word Pattern

5 Mar 2025

290. Word Pattern

문제

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. Specifically:

Each letter in pattern maps to exactly one unique word in s. Each unique word in s maps to exactly one letter in pattern. No two letters map to the same word, and no two words map to the same letter.

문제 사이트

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

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.

문제 해석

pattern의 단어를 하나씩 string s로 짝을 지어 전부 똑같은 짝으로 매치가 되는지 묻는 문제
s 는 하나의 공백으로 단어가 구분되어 있음

구현

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char, int> p_map;
        unordered_map<string, int> s_map;

        istringstream in(s);
        int i = 0;

        for(string word; in>>word; i++)
        {
            if(i == pattern.size() || p_map[pattern[i]] != s_map[word])
            {
                return false;
            }
            p_map[pattern[i]] = s_map[word] = i + 1;
        }
        return i == pattern.size();
    }
};

코드 해설

istringstream in(s);

이 문제를 푸는데 핵심 클래스
이 문제에서 어려웠던 점은 ‘어떻게 해야 string s 를 공백을 기준으로 나눌까?’ 였다

istringstream 이란??

istringstream는 C++ 에서 문자열을 입력 스트림처럼 다룰 수 있게 해주는 클래스이다.
istringstream는 기본적으로 std::string을 입력 스트림처럼 취급하여, 스트림 연산자(»)를 통해 데이터를 읽어올 수 있다.
보통 istringstream을 사용하여 문자열을 분리하거나, 숫자와 같은 데이터를 추출할 때 사용된다.
문자열을 입력 스트림처럼 다루기 때문에, 데이터를 구분자로 분리하거나 데이터를 읽고 쓰는 데 유용하다.(공백을 기준으로 나눈다.)

for(string word; in>>word; i++)

string word » string 객체 하나 생성
in»word » 스트림 연산자로 word에 s 를 공백 기준으로 나눈 in의 데이터들을 차례대로 넣는다.

p_map[pattern[i]] = s_map[word] = i + 1;

pattern의 char 와 s의 word를 매핑시켜준다.

if(i == pattern.size || p_map[pattern[i]] != s_map[word])

i 와 pattern의 크기가 다르다면 매핑이 되지 않는 것이 생길 것이다.
둘의 value 값이 다르다면 매핑이 맞지않아 문제에 어긋난다는 것이다.

290. Word Pattern

290. Word Pattern

문제

문제 해석

구현

코드 해설

istringstream 이란??

Table of Contents