侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【模拟】移除字母异位词后的结果数组

GabrielxD
2022-05-15 / 0 评论 / 0 点赞 / 192 阅读 / 832 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

5234. 移除字母异位词后的结果数组


给你一个下标从 0 开始的字符串 words ,其中 words[i] 由小写英文字符组成。

在一步操作中,需要选出任一下标 i ,从 words 中 删除 words[i] 。其中下标 i 需要同时满足下述两个条件:

  • 0 < i < words.length
  • words[i - 1]words[i] 是 字母异位词 。

只要可以选出满足条件的下标,就一直执行这个操作。

在执行所有操作后,返回 words 。可以证明,按任意顺序为每步操作选择下标都会得到相同的结果。

字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。例如,"dacb""abdc" 的一个字母异位词。

示例 1:

输入:words = ["abba","baba","bbaa","cd","cd"]
输出:["abba","cd"]
解释:
获取结果数组的方法之一是执行下述步骤:
- 由于 words[2] = "bbaa" 和 words[1] = "baba" 是字母异位词,选择下标 2 并删除 words[2] 。
  现在 words = ["abba","baba","cd","cd"] 。
- 由于 words[1] = "baba" 和 words[0] = "abba" 是字母异位词,选择下标 1 并删除 words[1] 。
  现在 words = ["abba","cd","cd"] 。
- 由于 words[2] = "cd" 和 words[1] = "cd" 是字母异位词,选择下标 2 并删除 words[2] 。
  现在 words = ["abba","cd"] 。
无法再执行任何操作,所以 ["abba","cd"] 是最终答案。

示例 2:

输入:words = ["a","b","c","d","e"]
输出:["a","b","c","d","e"]
解释:
words 中不存在互为字母异位词的两个相邻字符串,所以无需执行任何操作。

提示:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 10
  • words[i] 由小写英文字母组成

解题

方法一:模拟

思路

把所有单词放入集合(wordList)中,然后根据题意遍历模拟即可。 其中要判断两个字符串是否为字母异位词,把两个字符串转为字符数组,然后进行自然排序,比较新建字符串是否相等即可。

代码

class Solution {
    public List<String> removeAnagrams(String[] words) {
        int len = words.length;
        List<String> wordList = new ArrayList<>();
        for (String word : words) wordList.add(word);
        if (len < 2) return wordList;
        for (int i = len - 1; i >= 1; i--) {
            if (isAnagram(wordList.get(i), wordList.get(i - 1))) {
                wordList.remove(i);
            }
        }
        return wordList;
    }

    private boolean isAnagram(String str1, String str2) {
        char[] charArr1 = str1.toCharArray();
        char[] charArr2 = str2.toCharArray();
        Arrays.sort(charArr1);
        Arrays.sort(charArr2);
        return new String(charArr1).equals(new String(charArr2));
    }
}

优化

使用字符计数的方式判断是否为字母异位词

class Solution {
    public List<String> removeAnagrams(String[] words) {
        int len = words.length;
        List<String> wordList = new ArrayList<>();
        for (String word : words) wordList.add(word);
        if (len < 2) return wordList;
        for (int i = len - 1; i >= 1; i--) {
            if (isAnagram(wordList.get(i), wordList.get(i - 1))) {
                wordList.remove(i);
            }
        }
        return wordList;
    }

    private boolean isAnagram(String str1, String str2) {
        int[] freqs = new int[26];
        for (char ch : str1.toCharArray()) freqs[ch - 'a']++;
        for (char ch : str2.toCharArray()) {
            if (--freqs[ch - 'a'] < 0) return false;
        }
        for (int freq : freqs) {
            if (freq != 0) return false;
        }
        return true;
    }
}

优化

class Solution {
    public List<String> removeAnagrams(String[] words) {
        List<String> ans = new ArrayList<>();
        String prev = "";
        for (String word : words) {
            char[] charArr = word.toCharArray();
            Arrays.sort(charArr);
            String curr = new String(charArr);
            if (!curr.equals(prev)) ans.add(word);
            prev = curr;
        }
        return ans;
    }
}
0

评论区