.jpeg)
限制長度的雙指針。
背景知識
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
| public class Entry<K, V> {
private K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
// to store entries
public class Bucket {
private List<Entry> entries;
public Bucket() {
if(entries == null)
entries = new LinkedList<>();
}
public List<Entry> getEntries() {
return entries;
}
// linkedlist structure to add remove
public void addEntry(Entry entry) {
this.entries.add(entry);
}
public void removeEntry(Entry entry) {
this.entries.remove(entry);
}
}
public class HashMap<K, V> {
private int CAPACITY = 10;
private Bucket[] bucket;
private int size = 0;
public HashMap() {
this.bucket = new Bucket[CAPACITY];
}
// hash function
private int getHash(K key) {
return (key.hashCode() & 0xfffffff) % CAPACITY;
}
public boolean containsKey(K key) {
int hash = getHash(key);
return !(Objects.isNull(bucket[hash]) || Objects.isNull(getEntry(key)));
}
public void put(K key, V value) {
if(containsKey(key)) {
Entry entry = getEntry(key);
entry.setValue(value);
} else {
int hash = getHash(key);
if(bucket[hash] == null) {
bucket[hash] = new Bucket();
}
bucket[hash].addEntry(new Entry<>(key, value));
size++;
}
}
private Entry getEntry(K key) {
int hash = getHash(key);
for (int i = 0; i < bucket[hash].getEntries().size(); i++) {
Entry entry = bucket[hash].getEntries().get(i);
if(Entry.getKey().equals(key))
return entry;
}
return null;
}
public V get(K key) {
return containsKey(key) ? (V) getEntry(key).getValue() : null;
}
public void delete(K key) {
if(containsKey(key)) {
int hash = getHash(key);
bucket[hash].removeEntry(getEntry(key));
size--;
}
}
public int size() {
return size;
}
}
|
理解問題
給定雙字串s, p，p 是s子集，當p任意排列，求符合字串的index列表。
s = “cbaebabacd”
p = “abc”
[0,6]
思路視覺化
0: Counter(“cba”) == Counter(“abc”)
6: Counter(“bac”) == Counter(“abc”)
Java
TC: O(n)
SC: O(1)
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
| import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashMap;
class Array {
static HashMap Counter(String inputString){
HashMap<Character, Integer> charCountMap = new HashMap<Character, Integer>();
char[] strArray = inputString.toCharArray();
for (char c : strArray) {
if (charCountMap.containsKey(c)) {
charCountMap.put(c, charCountMap.get(c) + 1);
}else {
charCountMap.put(c, 1);
}
}
return charCountMap;
}
public static void main(String[] args) {
String s = "cbaebabacd", p = "abc";
ArrayList ret = new ArrayList();
for(int i = 0; i< s.length(); i++){
if(i+p.length()<s.length()){
String pair = s.substring(i,i+p.length());
if(Counter(p).keySet().equals(Counter(pair).keySet())){
ret.add(i);
}
}
}
System.out.println(ret);
}
}
>
java -cp /tmp/Xwe9oFFh1h Array
[0, 6]
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
| from collections import Counter
s, p = "cbaebabacd", "abc"
lp = len(p)
ret = []
for i in range(len(s)):
if Counter(p) == Counter(s[i:i+lp]):
ret.append(i)
print(ret)
> [0, 6]
|