Go Java 算法找不同
黄丫丫 人气:0找不同
给定两个字符串 s 和 t ,它们只包含小写字母。
字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
- 示例 1:
输入:s = "abcd", t = "abcde"
输出:"e"
解释:'e' 是那个被添加的字母。
- 示例 2:
输入:s = "", t = "y"
输出:"y"
提示:
0 <= s.length <= 1000
t.length == s.length + 1
- s 和 t 只包含小写字母
方法一:计数(Java)
首先遍历字符串 s,对其中的每个字符都将计数值加 1;然后遍历字符串 t,对其中的每个字符都将计数值减 1。
当发现某个字符计数值为负数时,说明该字符在字符串 t 中出现的次数大于在字符串 s 中出现的次数,因此该字符为被添加的字符。
class Solution { public char findTheDifference(String s, String t) { int[] cnt = new int[26]; for (int i = 0; i < s.length(); ++i) { char ch = s.charAt(i); cnt[ch - 'a']++; } for (int i = 0; i < t.length(); ++i) { char ch = t.charAt(i); cnt[ch - 'a']--; if (cnt[ch - 'a'] < 0) { return ch; } } return ' '; } }
N :字符串的长度
Σ :字符集
时间复杂度:O(N)
空间复杂度:O(∣Σ∣)
方法二:求和(Go)
本方法主要是利用了ASCII码,按照字符的ASCII码进行查找不同的字符。一次遍历计算出两个字符串的ASCII总和,根据差值既可以得出插入的字符
将字符串 s 中每个字符的 ASCII 码的值求和,得到 A_s
对字符串 t 同样的方法得到 A_t
两者的差值 A_t-A_s即代表了被添加的字符。
func findTheDifference(s, t string) byte { sum := 0 for _, ch := range s { sum -= int(ch) } for _, ch := range t { sum += int(ch) } return byte(sum) }
时间复杂度:O(N)
空间复杂度:O(1)
加载全部内容