[LeetCode] 809. Expressive Words

https://leetcode.com/problems/expressive-words/

Expressive Words - LeetCode

Expressive Words - Medium

 

String s와 String 벡터 words가 주어진다.

words 안의 word들을 다음과 같은 규칙으로 늘였을때, s가 될 수 있는 개수를 구하는 문제다.

규칙은 다음과 같다.

 

word의 알파벳들 또는 인접한 같은 알파벳들은 3개이상의 알파벳으로 늘이거나 원래 상태로 둘 수 있다.

예) zzyy의 z => z 또는 zzz 또는 zzzz, ....

zzyy의 zz => zz 또는 zzz 또는 zzzz, ...

 

풀이는 아래와 같다

먼저 pair<int, int>를 담는 벡터를 하나 만든다.

이는 현재 나온 알파벳과 그 개수를 담는 pair다.

s를 훑으며 현재 알파벳이 이전 알파벳과 같다면 pair의 개수를 ++,

다르면 기존 pair는 벡터에 담고, (현재 알파벳, 1) 로 새 pair를 만든다.

 

words 에 있는 word도 같은 방법으로 벡터를 만든다.

만든 후, s의 벡터와 길이가 같아야하고,

각각의 원소 (pair)의 알파벳도 같아야한다.

s 벡터 pair의 개수가 word 벡터 pair의 개수이상이며, 서로 같거나 s벡터 pair 개수가 3이상이어야한다.

 

전체 풀이 코드

 

class Solution {
public:
    int expressiveWords(string s, vector<string>& words) {
        words.insert(words.begin(), s);
        vector<pair<int,int>> v,t;
        pair<int, int> pre;
        int ret = 0;        
        for (int i=0,j; i<words.size(); i++) {
            string w = words[i];
            v.clear();
            for (j=0; j<w.size(); j++) {
                if (j==0) pre = make_pair(w[j]-'a',1);
                else if (w[j]!=w[j-1]) {
                        v.push_back(pre);
                        pre = make_pair(w[j]-'a',1);
                } else pre.second++;
            }
            v.push_back(pre);
            if (i==0) t=v;
            else if (v.size()==t.size()) {
                for (j=0; j<t.size(); j++) if (!(t[j].first == v[j].first && t[j].second >= v[j].second && (t[j].second==v[j].second || t[j].second>2))) break;
                if (j==t.size()) ret++;
            }
        }
        return ret;
    }
};