809. Expressive Words
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". Ifs = "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**.
Example 1:
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 size 3 or more.
Example 2:
Constraints:
1 <= s.length, words.length <= 1001 <= words[i].length <= 100sandwords[i]consist of lowercase letters.
Solution:
class Solution {
public int expressiveWords(String s, String[] words) {
int result = 0;
for (String word : words){
if (helper(s, word) == true){
result++;
}
}
return result;
}
private boolean helper(String s, String w){
int sIndex = 0;
int wIndex = 0;
while(sIndex < s.length() && wIndex < w.length()){
char curS = s.charAt(sIndex);
int curSCount = 0;
while(sIndex < s.length() && s.charAt(sIndex) == curS){
sIndex++;
curSCount++;
}
char curW = w.charAt(wIndex);
int curWCount = 0;
while(wIndex < w.length() && w.charAt(wIndex) == curW){
wIndex++;
curWCount++;
}
if (curW != curS){
return false;
}
if (curWCount > curSCount){
return false;
}
if (curWCount != curSCount && curSCount < 3){
return false;
}
}
if (sIndex == s.length() && wIndex == w.length()){
return true;
}else{
return false;
}
}
}
// TC: O(n^2)
// SC: O(1)
class Solution {
public int expressiveWords(String s, String[] words) {
int result = 0;
for (String word : words){
if (helper(s, word) == true){
result++;
}
}
return result;
}
private boolean helper(String s, String word){
int sIndex = 0;
int wIndex = 0;
while(wIndex < word.length() && sIndex < s.length()){
char curWLetter = word.charAt(wIndex);
int curWLetterCount = 0;
while(wIndex < word.length() && word.charAt(wIndex) == curWLetter){
wIndex++;
curWLetterCount++;
}
char curSLetter = s.charAt(sIndex);
int curSLetterCount = 0;
while(sIndex < s.length() && s.charAt(sIndex) == curSLetter){
sIndex++;
curSLetterCount++;
}
if (curWLetter != curSLetter){
return false;
}
if (curWLetterCount > curSLetterCount){
return false;
}
if (curWLetterCount != curSLetterCount && curSLetterCount < 3){
return false;
}
}
if (sIndex == s.length() && wIndex == word.length()){
return true;
}else{
return false;
}
}
}
// TC: O(n^2)
// SC: O(1)
class Solution {
public int expressiveWords(String s, String[] words) {
int count = 0;
// Input: s = "heeellooo", words = ["hello", "hi", "helo"]
// hello
for (String word : words){
if (isStretchy(s, word)){// heeellooo, hello
count++;
}
//
}
return count;
}
private boolean isStretchy(String s, String word){
int sIndex = 0;
int wordIndex = 0;
/*
s: h e e e l l o o o
si
word: h e l l o
wi
*/
while(sIndex < s.length() && wordIndex < word.length()){
// get the group in word
char wordLetter = word.charAt(wordIndex);// h
int wordLetterCount = 0;// count number of wordLetters in this group
while(wordIndex < word.length() && word.charAt(wordIndex) == wordLetter){
wordIndex++;// 1
wordLetterCount++; // 1
}
// get the group in s
char sLetter = s.charAt(sIndex);//h
// count number of sLetters in this group
int sLetterCount = 0;
while(sIndex < s.length() && s.charAt(sIndex) == sLetter){
sIndex++; //
sLetterCount++; // 1
}
// compare the groups
// if the letters don't match it's simply not possible
if (wordLetter != sLetter){ // same
return false;
}
// if count of letters in word is greater than those in s,
// then it's not possible, as we cannot delete letters from word
if (wordLetterCount > sLetterCount){
return false;
}// we can delete s not word
// if the counts don't match and required count
// ie sLetter count is less than 3 then it's not possible as the
// strtched group should be of size 3 at least
if (wordLetterCount != sLetterCount && sLetterCount < 3){
return false;
}
// for example like hello
// ll sLetterCount == 2 it can not be remove as helo
// it should make sure if repeat word should >= 3
// checking for this group is done, go for next group
}
// if we are here and we have reached the end of both s and word,
// it means it's stretchy
if (sIndex == s.length() && wordIndex == word.length()){
return true;
}else{
return false;
}
}
}
// O(N*M) O(1) N = number of words, M = maxlength of each word
感觉这题逻辑不会特别难 还是当天状态不对 耗时挺久的了
过个例子