【Leetcode 2273 】移除字母异位词后的结果数组 —— 三种版本，时间击败100%，空间击败100%

本文主要是介绍【Leetcode 2273 】移除字母异位词后的结果数组 —— 三种版本，时间击败100%，空间击败100%，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一个下标从 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] 由小写英文字母组成

第一版本

执行用时：97 ms, 在所有 Typescript 提交中击败了 - %的用户
内存消耗：59.62 MB, 在所有 Typescript 提交中击败了 - %的用户

/*
第一版本
https://leetcode.cn/u/cshappyeveryday/
执行用时：97 ms, 在所有 Typescript 提交中击败了 - %的用户
内存消耗：59.62 MB, 在所有 Typescript 提交中击败了 - %的用户
时间复杂度：O(n*m)
2024年8月30日 
*/
function removeAnagrams(words: string[]): string[] {const OFFSET = "a".charCodeAt(0);let sucP = 1;//二维数组存储每个字符的charCodeconst twoDimension = new Array(words.length).fill([]).map(() => new Array(26).fill(0));for (let i = 0; i < words.length; i++) {for (const char of words[i]) {twoDimension[i][char.charCodeAt(0) - OFFSET]++;}}for (let i = 1; i < words.length; i++) {//判断两个内容是否完全相等const diff = twoDimension[i].filter((n, j) => n === twoDimension[i - 1][j]);if (diff.length === twoDimension[i].length) continue;//在原数组上保存结果数据words[sucP++] = words[i];}return words.slice(0, sucP);
}

第二版本

执行用时：75 ms, 在所有 Typescript 提交中击败了 60.00 %的用户
内存消耗：55.16 MB, 在所有 Typescript 提交中击败了 100.00 %的用户

/*
第二版本
https://leetcode.cn/u/cshappyeveryday/
执行用时：75 ms, 在所有 Typescript 提交中击败了 60.00 %的用户
内存消耗：55.16 MB, 在所有 Typescript 提交中击败了 100.00 %的用户
时间复杂度：O(n*m)
2024年8月30日 
*/
function removeAnagrams2(words: string[]): string[] {const OFFSET = "a".charCodeAt(0);let sucP = 1;for (let i = 1; i < words.length; i++) {let curWordCode = new Array(26).fill(0);let preWordCode = new Array(26).fill(0);//每一次都计算当前与上一次的charCodefor (const word of words[i]) {curWordCode[word.charCodeAt(0) - OFFSET]++;}for (const word of words[i - 1]) {preWordCode[word.charCodeAt(0) - OFFSET]++;}const isSame = curWordCode.every((n, j) => n === preWordCode[j]);if (isSame) continue;words[sucP++] = words[i];}return words.slice(0, sucP);
}

最终版本

执行用时：67 ms, 在所有 Typescript 提交中击败了 100.00 %的用户

内存消耗：54.29 MB, 在所有 Typescript 提交中击败了 100.00 %的用户

/*
最终版本
https://leetcode.cn/u/cshappyeveryday/
执行用时：67 ms, 在所有 Typescript 提交中击败了 100.00 %的用户
内存消耗：54.29 MB, 在所有 Typescript 提交中击败了 100.00 %的用户
时间复杂度：O(n * m)
2024年8月30日 
*/
function removeAnagrams3(words: string[]): string[] {const OFFSET = "a".charCodeAt(0);let sucP = 1; //成功指针，指向words，该指针前面的元素都是结果let curWordCode = new Array<number>(26).fill(0); //当前 wordCodelet preWordCode = new Array<number>(26).fill(0); //上一个wordCode// 初始化 preWordCodefor (const word of words[0]) {preWordCode[word.charCodeAt(0) - OFFSET]++;}for (let i = 1; i < words.length; i++) {//去除和上一个相同的，注意：这里的去重与 Set() 去重不同。Set会将所有相同的去除，这里只针对相邻的两个if (words[i] === words[i - 1]) continue;curWordCode = new Array<number>(26).fill(0);for (const word of words[i]) {curWordCode[word.charCodeAt(0) - OFFSET]++;}//判断上一次成功的值与本次是否为 字母内容相同的const isSame =curWordCode.length === preWordCode.length &&curWordCode.every((n, j) => n === preWordCode[j]);//   是则证明不是 字母异位词，跳过if (isSame) continue;// 不是，则证明是 字母异位词，则 preWordCode 变成本次wordpreWordCode = [...curWordCode];//修改 结果，将成功指针后移words[sucP++] = words[i];}//依据 sucP 的位置返回结果return words.slice(0, sucP);
}

这篇关于【Leetcode 2273 】移除字母异位词后的结果数组 —— 三种版本，时间击败100%，空间击败100%的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！