My code:
public class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if (ransomNote == null || magazine == null) {
return false;
}
char[] c1 = ransomNote.toCharArray();
char[] c2 = magazine.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
int p1 = 0;
int p2 = 0;
while (p1 < c1.length && p2 < c2.length) {
if (c1[p1] == c2[p2]) {
int counter1 = 1;
p1++;
while (p1 < c1.length && c1[p1] == c1[p1 - 1]) {
p1++;
counter1++;
}
int counter2 = 1;
p2++;
while (p2 < c2.length && c2[p2] == c2[p2 - 1]) {
p2++;
counter2++;
}
if (counter1 > counter2) {
return false;
}
}
else {
p2++;
}
}
if (p1 < c1.length) {
return false;
}
else {
return true;
}
}
}
這道題目最簡(jiǎn)單的思路就是拿一個(gè) hashmap之類的來技術(shù)礁竞，然后很容易就做出來了怠硼。
時(shí)間復(fù)雜度： O(m + n)
空間復(fù)雜度： O(n)
那么，有沒有空間復(fù)雜度是 O(1)的解法呢迫悠？就是上面的解法
然后保持時(shí)間復(fù)雜度不變谆趾。雙指針
Anyway, Good luck, Richardo! -- 08/21/2016
