郑州建设银行网站房贷网点在哪,青柠视频免费版中文字幕,沈阳建站价格,企业建设营销型网站步骤本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服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] 只含有小写英文字母。 解法 遍历
不使用哈希表也不直接求出每个字符串的差分数组、再进行计数比较。思路很简单设当前位置为 i i i 则某个字符串 w o r d s [ j ] words[j] words[j] 当前位置的差分值由 w o r d s [ j ] [ i ] − w o r d s [ j ] [ i − 1 ] words[j][i] - words[j][i-1] words[j][i]−words[j][i−1] 得到。我们遍历所有位置并对每个位置下的、所有字符串的差分值进行比较。
设 w o r d s [ 0 ] [ i ] − w o r d s [ 0 ] [ i − 1 ] words[0][i] - words[0][i - 1] words[0][i]−words[0][i−1] 的差分值为 d d d 如果其他字符数组 w o r d s [ j ] words[j] words[j] 的差分值和 d d d 不等则累计不等的数量、记录对应下标 i d x idx idx 。
如果不等的数量为 0 0 0 说明这个位置 i i i 的所有差分值都相同如果不等的数量不为 0 0 0 不等的数量为 m − 1 m - 1 m−1 m m m 为字符数组个数根据题意只有一个字符串的差值数组不同则与众不同的就是 w o r d s [ 0 ] words[0] words[0] 否则唯一不同的是 w o r d s [ i d x ] words[idx] words[idx]
class Solution {public String oddString(String[] words) {int n words[0].length();for (int i 1; i n; i) {int d words[0].charAt(i) - words[0].charAt(i - 1);int idx 0, cnt 0;for (int j 1; j words.length; j) {int td words[j].charAt(i) - words[j].charAt(i - 1);if (td ! d) {idx j;cnt;} }if (cnt 0) continue;if (cnt words.length - 1) return words[0];return words[idx];}return ;}
}复杂度分析
时间复杂度 O ( n m ) O(n m) O(nm) n n n 为每个字符串的长度 m m m 为字符串数组的长度空间复杂度 O ( 1 ) O(1) O(1)
