情感丰富的文字【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≥3rs-i+1\geq3rs−i+1≥3。因此遍历words中的每个word，设置两个指针分别指向s和word的首部，如果字符相等，那么寻找该字符在s和word中的右边界，并判断是否需要进行扩展，以及能否进行扩展；如果字符不相等，那么一定不能进行转化，直接break

  • rs−i+1>rw−j+1rs - i + 1 > rw - j + 1rs−i+1>rw−j+1时，需要进行转化
    • rs−i+1≥3rs-i+1\geq3rs−i+1≥3时，不可以进行转化
    • rs−i+1<3rs-i+1\lt3rs−i+1<3时，可以进行转化
  • rs−i+1
  • rs−i+1==rw−j+1rs - i + 1 == rw - j + 1rs−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 >= 3i = 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;}
  }