[LeetCode] 242. Valid Anagram 验证变位词
LeetCode 验证 valid
2023-09-27 14:28:37 时间
Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1:
Input: s = "anagram", t = "nagaram" Output: true
Example 2:
Input: s = "rat", t = "car" Output: false
Note:
You may assume the string contains only lowercase alphabets.
Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?
给2个字符串s和t,写一个判断二者是否为变位词的函数。
解法1:利用HashMap记录s中出现的字母和数量,然后在用t的字母和数量来验证。
解法2:把两个string变为char array,对两个array进行排序,然后比较是否一样。
Java:
class Solution { public boolean isAnagram(String s, String t) { HashMap<Character, Integer> map = new HashMap<>(); // first time: store each s char and occurrence into map for(int i=0; i<s.length(); i++) { char sChar = s.charAt(i); map.put(sChar, map.getOrDefault(sChar, 0) + 1); } // second time: compare t char with map to see match or not for(int i=0; i<t.length(); i++) { char tChar = t.charAt(i); if(!map.containsKey(tChar)) return false; if(map.get(tChar) == 1) map.remove(tChar); else map.put(tChar, map.get(tChar) - 1); } return map.size() == 0 ? true : false; } }
Java:
public class Solution { public boolean isAnagram(String s, String t) { int[] alphabet = new int[26]; for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++; for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--; for (int i : alphabet) if (i != 0) return false; return true; } }
Python: T: O(n) S: O(1)
class Solution: def isAnagram(self, s, t): if len(s) != len(t): return False count = {} for c in s: if c.lower() in count: count[c.lower()] += 1 else: count[c.lower()] = 1 for c in t: if c.lower() in count: count[c.lower()] -= 1 else: count[c.lower()] = -1 if count[c.lower()] < 0: return False return True
Python: wo
class Solution(object): def isAnagram(self, s, t): """ :type s: str :type t: str :rtype: bool """ a = [0] * 256 for i in s: a[ord(i)] += 1 b = [0] * 256 for j in t: b[ord(j)] += 1 return a == b
Python: T: O(n) S: O(1)
class Solution: def isAnagram3(self, s, t): if len(s) != len(t): return False count = collections.defaultdict(int) for c in s: count[c] += 1 for c in t: count[c] -= 1 if count[c] < 0: return False return True
Python:
def isAnagram1(self, s, t): dic1, dic2 = {}, {} for item in s: dic1[item] = dic1.get(item, 0) + 1 for item in t: dic2[item] = dic2.get(item, 0) + 1 return dic1 == dic2
Python: T: O(nlogn) S: O(n)
class Solution: def isAnagram(self, s, t): return sorted(s) == sorted(t)
C++:
class Solution { public: bool isAnagram(string s, string t) { if (s.size() != t.size()) return false; int m[26] = {0}; for (int i = 0; i < s.size(); ++i) ++m[s[i] - 'a']; for (int i = 0; i < t.size(); ++i) { if (--m[t[i] - 'a'] < 0) return false; } return true; } };
All LeetCode Questions List 题目汇总
相关文章
- 【LeetCode】数组中的第K个最大元素 [M](快速排序)
- 【LeetCode】两数相加
- LeetCode_字符串_中等_151.颠倒字符串中的单词
- LeetCode_字符串反转_简单_557. 反转字符串中的单词 III
- LeetCode_滑动窗口_中等_395.至少有 K 个重复字符的最长子串
- LeetCode_动态规划_困难_312.戳气球
- LeetCode_双指针_简单_26.删除有序数组中的重复项
- leetcode 222. 完全二叉树的节点个数
- leetcode 春季编程大赛-个人赛
- LeetCode-104. 二叉树的最大深度(java)
- [LeetCode] 504. Base 7 基数七
- [LeetCode] 676. Implement Magic Dictionary 实现神奇字典
- [LeetCode] 65. Valid Number 验证数字
- [LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树
- [LeetCode] 460. LFU Cache 最近最不常用页面置换缓存器
- [LeetCode] 212. Word Search II 词语搜索 II
- [LeetCode] 15. 3Sum 三数之和