情感丰富的文字【LC809】

Sometimes people repeat letters to represent extra feeling. For example:

• "hello" -> "heeellooo"

• "hi" -> "hiiii"

In these strings like "heeellooo", we have groups of adjacent letters that are all the same: "h", "eee", "ll", "ooo".

You are given a string s and an array of query strings words. A query word is stretchy if it can be made to be equal to s by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is three or more.

• For example, starting with "hello", we could do an extension on the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has a size less than three. Also, we could do another extension like "ll" -> "lllll" to get "helllllooo". If s = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -> "hellooo" -> "helllllooo" = s.

Return the number of query strings that are stretchy.

原来来来外国人人人人都是这样说话话话话的吗吗吗吗

全校静默的第一天天天天

• 思路：统计words中可以转化为s的个数，转化方式为当s[i,rs] == word[j,rw]时，可以扩展word中字符使其与s相等，条件为rs−i+1≥3。因此遍历words中的每个word，设置两个指针分别指向s和word的首部，如果字符相等，那么寻找该字符在s和word中的右边界，并判断是否需要进行扩展，以及能否进行扩展；如果字符不相等，那么一定不能进行转化，直接break

。rs−i+1>rw−j+1时，需要进行转化

• rs−i+1≥3时，不可以进行转化

• rs−i+1<3时，可以进行转化

。rs−i+1<rw−j+1时，不可以进行转化，break

。rs−i+1==rw−j+1时，不需要进行转化，继续判断

• 实现：

当word的长度大于s的长度时，那么一定不可以进行转化

class Solution {
    public int expressiveWords(String s, String[] words) {
        int len = s.length();
        int count = 0;
        for (String word : words){
            int lenWord = word.length();
            if (lenWord > len){
                break;
            }
            int i = 0, j = 0;
            while (i < len && j < lenWord && s.charAt(i) == word.charAt(j)){             
                int rightS = getRightBorder(s,i);
                int rightWord = getRightBorder(word,j);
                if (rightS - i + 1 < rightWord - j + 1){
                    break;
                }else if (rightS - i + 1 > rightWord - j + 1 && rightS - i + 1 < 3){
                    break;
                }
                // rightS - i + 1 == rightWord - j + 1 
                // rightS - i + 1 > rightWord - j + 1 && rightS - i + 1 >= 3
                i = rightS + 1;
                j = rightWord + 1;
                if (i == len && j == lenWord){
                    count++;
                }           
            }
        }
        return count;
    }
    public int getRightBorder(String s,int left){
        int right = left;
        char c = s.charAt(left);
        while (right + 1 < s.length() && s.charAt(right + 1) == c){
            right++;
        }
        return right;
    }
}