(Leet Code c++)Word Pattern

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.

 

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

Example 4:

Input: pattern = "abba", s = "dog dog dog dog" Output: false

 

Constraints:

• 1 <= pattern.length <= 300
• pattern contains only lower-case English letters.
• 1 <= s.length <= 3000
• s contains only lower-case English letters and spaces ' '.
• s does not contain any leading or trailing spaces.
• All the words in s are separated by a single space.

map을 활용한 문제 풀이.

 

주어진 s를 토크나이징 하여 단어를 나누도록 한다.

while문으로 토크나이징 된 단어를 pattern과 같은 배열인지 확인한다.

 

우선 token이 map의 key로 존재하지 않고, 현재 pattern의 알파벳이 쓰인 적이 없으면

token을 키로 가지는 pattern[index]를 저장한다.(단어에 해당하는 알파벳 저장)

그리고 알파벳을 사용했기 때문에 해당 알파벳 사용 여부를 true로 바꾼다.

 

만약 token이 map의 key로 존재하거나, 현재 알파벳이 쓰인 적이 있다면

token에 해당하는 value와 알파벳 패턴이 같은지 확인하도록 한다.

 

같지 않다면 바로 false를 리턴!

 

while문을 빠져나오게 된다면 한번 더 검사하도록 한다.

index의 크기가 pattern 문자열의 크기보다 작다면 false를 리턴.

(pattern은 띄어쓰기가 존재하지 않기 때문에, 토크나이징 된 횟수와 index가 일치해야 한다.)

 

아니라면 true를 리턴하도록 한다.

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        map<string, char> m;
        string token;
        stringstream ss(s);
        int index = 0;
        vector<bool> check(26, false);
        
        while(ss >> token){
            if(m.find(token) == m.end() && !check[pattern[index] - 'a']){
                m[token] = pattern[index];
                check[pattern[index] - 'a'] = true;
            }
            else{
                if(m[token] != pattern[index]){
                    return false;
                }
            }
            index++;
        }
        
        if(index < pattern.size()){
            return false;
        }
        
        return true;
    }
};