資訊專欄INFORMATION COLUMN
摘要：建立一個(gè)長(zhǎng)度為的數(shù)組，統(tǒng)計(jì)所有個(gè)字符在出現(xiàn)的次數(shù)，然后減去這些字符在中出現(xiàn)的次數(shù)。否則，循環(huán)結(jié)束，說(shuō)明所有字符在和中出現(xiàn)的次數(shù)一致，返回。
Program
Write a method anagram(s,t) to decide if two strings are anagrams or not.
ExampleGiven s="abcd", t="dcab", return true.
ChallengeO(n) time, O(1) extra space
Note建立一個(gè)長(zhǎng)度為256的數(shù)組，統(tǒng)計(jì)所有256個(gè)字符在String s出現(xiàn)的次數(shù)，然后減去這些字符在String t中出現(xiàn)的次數(shù)。若某個(gè)字符統(tǒng)計(jì)次數(shù)最終小于0，說(shuō)明t中這個(gè)字符比s中更多，返回false。否則，循環(huán)結(jié)束，說(shuō)明所有字符在s和t中出現(xiàn)的次數(shù)一致，返回true。
SolutionBrute 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 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.
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65696.html
摘要：首先將兩個(gè)字符串化成字符數(shù)組，排序后逐位比較，確定它們等長(zhǎng)且具有相同數(shù)量的相同字符。然后，從第一個(gè)字符開(kāi)始向后遍歷，判斷和中以這個(gè)坐標(biāo)為中點(diǎn)的左右兩個(gè)子字符串是否滿足第一步中互為的條件設(shè)分為和，分為和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...
摘要：就不說(shuō)了，使用的解法思路如下建立，對(duì)應(yīng)該元素的值與之差，對(duì)應(yīng)該元素的。然后，循環(huán)，對(duì)每個(gè)元素計(jì)算該值與之差，放入里，。如果中包含等于該元素值的值，那么說(shuō)明這個(gè)元素正是中包含的對(duì)應(yīng)的差值。返回二元數(shù)組，即為兩個(gè)所求加數(shù)的序列。 Problem Given an array of integers, find two numbers such that they add up to a s...
Problem You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1s digit is at the head of the list. Write a f...
Problem Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute dif...
Problem Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at ...
閱讀 1318·2021-11-04 16:09
閱讀 3523·2021-10-19 11:45
閱讀 2411·2021-10-11 10:59
閱讀 1024·2021-09-23 11:21
閱讀 2776·2021-09-22 10:54
閱讀 1152·2019-08-30 15:53
閱讀 2622·2019-08-30 15:53
閱讀 3491·2019-08-30 12:57
