05 August 2008
Sometimes people repeat letters to represent extra feeling. For example:
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.
本题中的【不可扩张】的 3 种情况
c1, c2 不同 c2, c2 长度不同，而且 c1 长度只有 2，无法被扩张 c2 长度 > c1 长度
<比较模板> while(A 没完 && B 没完) A 的当前字符 B 的当前字符 A 的当前字符长度 B 的当前字符长度 判读符合比较条件吗 判断 A B 都走完了吗 ```java class Solution { public int expressiveWords(String S, String[] words) { if (S == null || S.length() == 0 || words == null || words.length == 0) { return 0; } int count = 0; for (String word : words) { if (isStrechy(S, word)) count++; } return count; } // 判断 t 是否可以扩张成 s private boolean isStrechy(String s, String t) { int n = s.length(), m = t.length(); if (n < m) return false; int i = 0, j = 0; while (i < n && j < m) { char c1 = s.charAt(i); char c2 = t.charAt(j); // 优化：可以在这之后直接判断字符是否相等。 // c1几个 int cnt1 = 0; while (i < n && s.charAt(i) == c1) { i++; cnt1++; } // c2几个 int cnt2 = 0; while (j < m && t.charAt(j) == c2) { j++; cnt2++; } /** 3 种无法扩张的情况 1. c1, c2 不同 2. c2, c2 长度不同，而且 c1 长度只有 2，无法被扩张 3. c2 长度 > c1 长度 **/ if (c1 != c2 || cnt1 < cnt2 || cnt1 <= 2 && cnt1 != cnt2) return false; } // 判断 s, t 都走完了吗？ return i == s.length() && j == t.length(); } } ```