Daily LeetCode – day0119 0809. Expressive Words

import java.util.ArrayList;

// 0809. Expressive Words
class Solution {
    public int expressiveWords(String s, String[] words) {
        ArrayList<CharAndQuantity> charAndQuantities = new ArrayList<>();
        char[] sArray = s.toCharArray();
        int len = sArray.length;
        charAndQuantities.add(new CharAndQuantity(sArray[0], 1));
        for (int i = 1; i < len; ++i) {
            if (sArray[i] != sArray[i - 1]) {
                charAndQuantities.add(new CharAndQuantity(sArray[i], 1));
            } else {
                ++charAndQuantities.get(charAndQuantities.size() - 1).q;
            }
        }
        int ans = 0;
        for (String word : words) {
            ans += isStretchy(word, charAndQuantities);
        }
        return ans;
    }

    private int isStretchy(String word, ArrayList<CharAndQuantity> charAndQuantities) {
        char[] charArray = word.toCharArray();
        int len = charArray.length;
        char currentChar;
        int currentQuantity;
        int j = 0;
        for (int i = 0; i < len; ) {
            currentChar = charArray[i];
            currentQuantity = 0;
            while (i < len && charArray[i] == currentChar) {
                ++currentQuantity;
                ++i;
            }
            if (j < charAndQuantities.size()) {
                CharAndQuantity charAndQuantity = charAndQuantities.get(j);
                if (charAndQuantity.c == currentChar && (charAndQuantity.q > 2 || charAndQuantity.q == currentQuantity) && charAndQuantity.q >= currentQuantity) {
                    ++j;
                } else {
                    return 0;
                }
            } else {
                return 0;
            }
        }
        if (j == charAndQuantities.size()) return 1;
        return 0;
    }
}

class CharAndQuantity {
    char c;
    int q;

    public CharAndQuantity(char c, int q) {
        this.c = c;
        this.q = q;
    }
}
学习笔记:
这是一道字符串数组的题目。
我们需要使用自顶向下的编程思路,原始思路是使用双指针来遍历两个字符串。
但是字符串s其实是不变的,所以可以提前用辅助的对象数组统计好字符和出现次数来加速。
要考虑的条件比较多,字符得对上,数量可以刚好,也可以三个以上,但又不能比原先的还多。
用了辅助数组还需要考虑数组的越界(不过双指针也是需要另外一个字符串的越界的)。
还要考虑word走完,s还没有走完的情况。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注