制定网站建设规划书,查看网页源代码,网站建设需要注意什么 知乎,wordpress 大众点评来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
给你一个字符串数组 words #xff0c;每一个字符串长度都相同#xff0c;令所有字符串的长度都为 n 。
每个字符串 words[i] 可以被转化为一个长度为 n - 1 的 差值整数数组 difference[i] …来源力扣LeetCode
描述
给你一个字符串数组 words 每一个字符串长度都相同令所有字符串的长度都为 n 。
每个字符串 words[i] 可以被转化为一个长度为 n - 1 的 差值整数数组 difference[i] 其中对于 0 j n - 2 有 difference[i][j] words[i][j1] words[i][j] 。注意两个字母的差值定义为它们在字母表中 位置 之差也就是说 a 的位置是 0 b 的位置是 1 z 的位置是 25 。
比方说字符串 acb 的差值整数数组是 [2 - 0, 1 - 2] [2, -1] 。
words 中所有字符串 除了一个字符串以外 其他字符串的差值整数数组都相同。你需要找到那个不同的字符串。
请你返回 words 中 差值整数数组 不同的字符串。
示例 1
输入words [adc,wzy,abc]
输出abc
解释
- adc 的差值整数数组是 [3 - 0, 2 - 3] [3, -1] 。
- wzy 的差值整数数组是 [25 - 22, 24 - 25] [3, -1] 。
- abc 的差值整数数组是 [1 - 0, 2 - 1] [1, 1] 。
不同的数组是 [1, 1]所以返回对应的字符串abc。示例 2
输入words [aaa,bob,ccc,ddd]
输出bob
解释除了 bob 的差值整数数组是 [13, -13] 以外其他字符串的差值整数数组都是 [0, 0] 。提示
3 words.length 100n words[i].length2 n 20words[i] 只含有小写英文字母。
方法遍历
思路与算法
注意到字符串数组 words 的长度 m 最小为 3因此我们记 diff0 diff1diff2 分别是 words0 words1words2 的差值整数数组基于此分情况讨论
如果 diff0 diff1 那么我们遍历 words2 ∼ wordsm−1 找到第一个差值整数数组不等于 diff0 的字符串即可。否则如果 diff0 ≠ diff1 那么我们只需判断 diff0 是否等于 diff2 即可。如果等于则足以说明 words1 是唯一一个与其他字符串的差值整数数组都不相同的字符串因此直接返回 words1。反之如果 diff0 不等于 diff2 则返回 words0。
代码
class Solution {
public:vectorint get(string word) {vectorint diff(word.size() - 1);for (int i 0; i 1 word.size(); i) {diff[i] word[i 1] - word[i];}return diff;}string oddString(vectorstring words) {auto diff0 get(words[0]);auto diff1 get(words[1]);if (diff0 diff1) {for (int i 2; i words.size(); i) {if (diff0 ! get(words[i])) {return words[i];}}}return diff0 get(words[2]) ? words[1] : words[0];}
};执行用时0ms, 在所有 C 提交中击败了100.00%的用户 内存消耗7 MB, 在所有 C 提交中击败了93.75%的用户 复杂度分析 时间复杂度O(mn)其中 m 是 words 的长度n 是 words 中字符串的长度。计算每个字符串的差值整数数组复杂度为 O(n)比较两个字符串的差值整数数组是否相同的复杂度为 O(n)过程中最多比较 m 次因此总体复杂度为 O(mn)。 空间复杂度O(n)。过程中最多会同时存在 3 个长度为 n 的差值整数数组因此空间复杂度为 O(n)。 authorLeetCode-Solution
