【每日一题Day38】LC809情感丰富的文字 | 双指针 模拟

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

  • $rs-i+1>rw-j+1$时，需要进行转化
    • $rs-i+1\ge 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;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40