2273. Find Resultant Array After Removing Anagrams

Problem

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.

In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams, and delete words[i] from words. Keep performing this operation as long as you can select an index that satisfies the conditions.

Return words after performing all operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same result.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".

Solution

由于只用查看上一个元素。
记录一个prev[]数组记录上一个元素的字符情况。
遍历words，用数组bin[]统计每个字母出现的次数，同时减去prev数组的统计数字。
如果数组中的每个统计结果都为0，则是上一个字符串的Anagram。
否则是一个新的字符串，将其加入结果。
然后将上一个数组prev更新为当前的统计数组bin[]。

Code

class Solution {
    public List<String> removeAnagrams(String[] words) {
        int[] prev = new int[26];
        
        List<String> ans = new ArrayList<>();
        
        for(String word : words){
            int[] bin = new int[26];
            char[] chars = word.toCharArray();
            for(int i = 0; i < chars.length; i++){
                prev[chars[i]-'a']--;
                bin[chars[i]-'a']++;
            }
            if(!allZero(prev)){
                ans.add(word);
            }
            prev = bin;
        }
        return ans;
    }
    
    private boolean allZero(int[] bin){
        for(int num : bin){
            if(num != 0) return false;
        }
        return true;
    }
}