[LintCode/LeetCode] Two Strings are Anagrams/Valid Anagram
文章目录
Program
Write a method anagram(s,t) to decide if two strings are anagrams or not.
Example
Given s="abcd", t="dcab", return true.
Challenge
O(n) time, O(1) extra space
Note
建立一个长度为256的数组,统计所有256个字符在String s出现的次数,然后减去这些字符在String t中出现的次数。若某个字符统计次数最终小于0,说明t中这个字符比s中更多,返回false。否则,循环结束,说明所有字符在s和t中出现的次数一致,返回true。
Solution
Brute Force
O(nlogn)
public class Solution {
public boolean isAnagram(String s, String t) {
char[] schar = s.toCharArray();
char[] tchar = t.toCharArray();
Arrays.sort(schar);
Arrays.sort(tchar);
return String.valueOf(schar).equals(String.valueOf(tchar));
}
}
HashMap
public class Solution {
public boolean anagram(String s, String t) {
int[] count = new int[256];
for (int i = 0; i < s.length(); i++) {
count[(int) s.charAt(i)]++;
}
for (int i = 0; i < s.length(); i++) {
count[(int) t.charAt(i)]--;
if (count[(int) t.charAt(i)] < 0) return false;
}
return true;
}
}
Slow HashMap
public class Solution {
public boolean isAnagram(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
Character ch = s.charAt(i);
if (map.containsKey(ch)) {
map.put(ch, map.get(ch)+1);
}
else map.put(ch, 1);
}
for (int i = 0; i < t.length(); i++) {
Character ch = t.charAt(i);
if (!map.containsKey(ch)) return false;
map.put(ch, map.get(ch)-1);
if (map.get(ch) < 0) return false;
}
for (int i = 0; i < s.length(); i++) {
Character ch = s.charAt(i);
if (map.get(ch) != 0) return false;
}
return true;
}
}
Follow up: contains unicode chars?
Just give the count[] array space of 256.
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论