首页 > > 程序设计 > C/C++ >

leetcode笔记（五）809. Expressive Words

2018-06-29 06:14:56来源：博客园阅读 ()

题目描述

Sometimes people repeat letters to represent extra feeling, such as "hello" -> "heeellooo", "hi" -> "hiiii". Here, we have groups, of adjacent letters that are all the same character, and adjacent characters to the group are different. A group is extended if that group is length 3 or more, so "e" and "o" would be extended in the first example, and "i" would be extended in the second example. As another example, the groups of "abbcccaaaa" would be "a", "bb", "ccc", and "aaaa"; and "ccc" and "aaaa" are the extended groups of that string.

For some given string S, a query word is stretchy if it can be made to be equal to S by extending some groups. Formally, we are allowed to repeatedly choose a group (as defined above) of characters c, and add some number of the same character c to it so that the length of the group is 3 or more. Note that we cannot extend a group of size one like "h" to a group of size two like "hh" - all extensions must leave the group extended - ie., at least 3 characters long.

Given a list of query words, return the number of words that are stretchy.

Example:
Input: 
S = "heeellooo"
words = ["hello", "hi", "helo"]
Output: 1
Explanation: 
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not extended.

Notes:

0 <= len(S) <= 100.
0 <= len(words) <= 100.
0 <= len(words[i]) <= 100.
S and all words in words consist only of lowercase letters

解题思路

题目描述挺多～题目属于第一眼简单题，知道属于字符串匹配，知道最好用正则表达式。但是无奈记不清C++ regex类的用法。

所以，就退而求其次，用最笨的思路实现下字符串匹配。主要思路：

建立规则，根据标准字符串S，计算字符串匹配的规则，表示为字母和字母次数的pair。如
```
S = "heeellooo" --> [<h, 1>, <e, 3>, <l, 2>, <o, 3>]
```
应用规则，根据规则，判断每个待测字符串是否满足标准。其实就是根据字母的次数决定字母在待测字符串的正确存在。具体如下：
- 出现次数小于3：根据题意可知，这组字母不属于扩展组，所以待测字符串中必须有等于该次数的该字母。
- 出现次数大于等于3：属于扩展组，待测字符串中可以有小于等于该次数的该字母。

示例代码

class Solution {
public:
    int expressiveWords(string S, vector<string>& words) {
        int size = S.length();
        char before = '\0';
        int counter = 0;
        vector<pair<int, int>> rules;
        for(int i = 0; i < size; i++)
        {
            if(S[i] == before)
            {
                counter += 1;
            }
            else
            {
                // update rules
                if(counter > 0)
                    rules.push_back(make_pair(before, counter));
                
                // restart counter
                before = S[i];
                counter = 1;
            }
        }
        // update rules
        if(counter > 0)
            rules.push_back(make_pair(before, counter));
        
        int ruleSize = rules.size();
        int result = 0;
        size = words.size();
        for(int i = 0; i < size; i++)
        {
            // if equal
            if(words[i] == S)
            {
                result += 1;
                continue;
            }
            
            // validate each word against rules
            int wordSize = words[i].length();
            bool isOk = true;
            int currIndex = 0;
            for(int j = 0; j < ruleSize; j++)
            {
                char curr = rules[j].first;
                counter = rules[j].second;
                
                int currCounter = 0;
                // counter this character in words vector
                while(currIndex < wordSize && words[i][currIndex] == curr)
                {
                    currCounter += 1;
                    currIndex += 1;
                }
                // non-extended(min)
                if(counter < 3)
                {
                    if(currCounter != counter)
                    {
                        isOk = false;
                        break;
                    }
                }
                // extended
                else
                {
                    if(currCounter > counter)
                    {
                        isOk = false;
                        break;
                    }
                }
                
            }
            if(isOk)
            {
                result += 1;
            }
        }
        
        return result;
    }
};