欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 汽车 > 新车 > 【Leetcode 2273 】 移除字母异位词后的结果数组 —— 三种版本,时间击败100%,空间击败100%

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

2025/9/7 18:42:28 来源:https://blog.csdn.net/Caoshuang_/article/details/141724045  浏览:    关键词:【Leetcode 2273 】 移除字母异位词后的结果数组 —— 三种版本,时间击败100%,空间击败100%

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

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

  1. 0 < i < words.length
  2. 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);
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词