寻找添加的字母：字符串比较算法与Java实现

"寻找添加的字母：字符串比较算法与Java实现"\n\n本文提供了一种有效的算法来找出给定两个字符串s和t中添加的字母。字符串t是由s中的字母随机打乱之后，在随机的一个位置添加一个字母生成的。算法使用HashMap记录字符串s中每个字符出现的次数，并遍历字符串t进行比较，最后找出添加的字母。同时提供了详细的代码实现和复杂度分析。\n\n问题描述\n\n给定两个字符串s和t，它们只包含小写字母。字符串t是由s中的字母随机打乱之后，在随机的一个位置添加一个字母生成的。请找出那个添加的字母。\n\n示例：\n\n\n\ns = \"abcd\"\nt = \"baedc\"\n\n输出：e\n\n\n思路：\n\n1. 使用HashMap记录字符串s中每个字符出现的次数。\n2. 遍历字符串t，对于每个字符，如果在HashMap中存在并且次数大于0，则将其次数减1。\n3. 最后剩下的字符即为添加的字母。\n\n代码实现 (Java)：\n\njava\nimport java.util.HashMap;\n\npublic class Solution {\n public char findTheDifference(String s, String t) {\n HashMap<Character, Integer> map = new HashMap<>();\n for (char c : s.toCharArray()) {\n map.put(c, map.getOrDefault(c, 0) + 1);\n }\n for (char c : t.toCharArray()) {\n if (map.containsKey(c) && map.get(c) > 0) {\n map.put(c, map.get(c) - 1);\n } else {\n return c;\n }\n }\n return ' ';// 理论上不会出现这种情况\n }\n}\n\n\n复杂度分析：\n\n- 时间复杂度：遍历字符串s和t，时间复杂度为O(max(n, m))，其中n和m分别为字符串s和t的长度。\n- 空间复杂度：使用了HashMap来存储字符出现的次数，空间复杂度为O(n)，其中n为字符串s的长度。