首页 > 代码库 > LeetCode 389. Find the Difference
LeetCode 389. Find the Difference
Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s and then add one more letter at a random position.
Find the letter that was added in t.
Example:
Input: s = "abcd" t = "abcde" Output: e Explanation: ‘e‘ is the letter that was added.
本题最直观的思路为排序后对s和t逐位进行比较。故得以下代码:
1 class Solution 2 { 3 public: 4 char findTheDifference(string s, string t) 5 { 6 sort(s.begin(), s.end()); 7 sort(t.begin(), t.end()); 8 for(int i = 0; i < s.size(); i++) 9 { 10 if(s[i] == t[i]) 11 { 12 continue; 13 } 14 else 15 { 16 return t[i]; 17 } 18 } 19 return t[t.size() - 1]; 20 } 21 };
由于排序复杂度过高,于是查询别的解法发现,可以建立一个字母表,s出现一次字母表对应位置+1,t中出现一次对应位置-1。那么只在t中出现的字母的位置为-1。代码如下:
1 public char findTheDifference(String s, String t) { 2 if(s == null || s.length() == 0) 3 return t.charAt(0); 4 int[] letters = new int[26]; 5 for(int i = 0; i < s.length(); i++){ 6 int sPosition = s.charAt(i) - ‘a‘; 7 int tPosition = t.charAt(i) - ‘a‘; 8 letters[sPosition]++; 9 letters[tPosition]--; 10 } 11 int tPosition = t.charAt(t.length()-1) - ‘a‘; 12 letters[tPosition]--; 13 char res = ‘a‘; 14 for(int i = 0; i < letters.length; i++){ 15 if(letters[i] == -1){ 16 res+= i; 17 break; 18 } 19 } 20 return res; 21 }
LeetCode 389. Find the Difference
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。