[LeetCode/easy] Word Pattern

 

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

Word Pattern - LeetCode

 

pattern과 v의 단어를 짝지어준다. (a-dog, b-cat) 이런 식으로.

 

1. 문자열 s을 공백 없이 단어들만 v에 넣어주기 (getline, sstream)

2. 문자열 v와 pattern의 길이 다르면 바로 return false

3. checkS()를 통해 현재 문자열 v와 다른 패턴이랑 짝지어진 적이 있는지 체크한다.

     만약 p[i]. second == str && p[i]. first!= c 라면 return false (짝짓는 vector에서 문자열을 찾았는데 패턴이 다른 경우)

4.  findPair()를 통해 짝지어진 패턴이 있는지 확인하고 있다면 그 패턴의 인덱스 return 없으면 return -1

5. 짝이 없다면, p에 {패턴, 문자열} 넣기

6. 짝이 있는 경우인데 이 패턴과 짝지어지는 문자열과 다르다면 return false

 

vector<pair<char, string>> p;

int findPair(char s){
    for(int i=0; i<p.size(); i++){
        if(p[i].first == s) return i;
    }
    return -1;
}

bool checkS(char c, string str){
    for(int i=0; i<p.size(); i++){
        if(p[i].second == str){
            if(p[i].first != c) return false;
        }
    }
    return true;
}

bool wordPattern(string pattern, string s) {
    bool answer = true;
    stringstream ss(s);
    string buffer;
    vector<string> v;
    while(getline(ss, buffer, ' ')) v.push_back(buffer);
    
    if(pattern.size() != v.size()) return false;
    
    for(int i=0; i<pattern.size(); i++){
        int index = findPair(pattern[i]);
        if(!checkS(pattern[i], v[i])) return false;
        if(index == -1){ //짝이 없다면
            p.push_back({pattern[i], v[i]});
            
        }else{
            if(p[index].second != v[i]) return false;
        }
    }
    return answer;
}