-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCanConstruct.java
More file actions
90 lines (77 loc) · 2.46 KB
/
CanConstruct.java
File metadata and controls
90 lines (77 loc) · 2.46 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package leecode;
import java.util.HashMap;
public class CanConstruct {
public static void main(String[] args) {
// TODO Auto-generated method stub
String a = "bdjijj";
String b = "aifbigejbibiefgeffhabgeejdbiajgaahjefhdegafhfcigjaecbfiechadiehhfcejhhfbbdjheecfaijdba";
System.out.println(canConstruct(a, b));
}
/**
* TLE
* @param ransomNote
* @param magazine
* @return
*/
public static boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
boolean result = true;
if(null == ransomNote && null == magazine){
return false;
}
for(int i = 0; i < magazine.length(); i++){
if(!map.containsKey(magazine.charAt(i))){
map.put(magazine.charAt(i), 1);
}else{
int count = map.get(magazine.charAt(i));
map.put(magazine.charAt(i), count + 1);
}
}
for(int j = 0; j < ransomNote.length(); j++){
if(map.containsKey(ransomNote.charAt(j))){
int count = map.get(ransomNote.charAt(j));
if(0 == count){
result = false;
}else{
map.put(ransomNote.charAt(j), count -1);
}
}else{
result = false;
}
}
return result;
}
public static boolean canConstruct1(String ransomNote, String magazine) {
boolean result = true;
for(int i = 0; i < ransomNote.length(); i++){
if(magazine.contains(String.valueOf(ransomNote.charAt(i)))){
int index = magazine.indexOf(ransomNote.charAt(i));
int endIndex = magazine.length();
magazine = magazine.substring(0, index) + magazine.substring(index + 1, endIndex);
}else{
result = false;
}
}
return result;
}
/**
* 在看问题note，发现两个目标string都只包含contain only lowercase letters.
* 故考虑直接用一维数组
* @param ransomNote
* @param magazine
* @return
*/
public static boolean canConstruct2(String ransomNote, String magazine) {
boolean result = true;
int[] arr = new int[26];
for (int i = 0; i < magazine.length(); i++) {
arr[magazine.charAt(i) - 'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
if(--arr[ransomNote.charAt(i)-'a'] < 0) {
result = false;
}
}
return result;
}
}