Lintcode_HighFreq/Chapter3/647.substring-anagrams.java at master · ganjingcatherine/Lintcode_HighFreq · GitHub

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// O(n)
public class Solution {
    /*
     * @param s: a string
     * @param p: a string
     * @return: a list of index
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        if (s == null || s.length() == 0 || p == null || p.length() == 0) {
            return ans;
        }

        if (s.length() < p.length()) {
            return ans;
        }

        // The difference map between current substring in s and p.
        // s - p
        int[] diff = new int[256];
        char[] sc = s.toCharArray();
        char[] pc = p.toCharArray();

        // Initial map
        for (int i = 0; i < p.length(); i++) {
            diff[pc[i]]--;
            diff[sc[i]]++;
        }

        // Current difference sum
        int sum = 0;
        for (int v : diff) {
            sum += Math.abs(v);
        }

        if (sum == 0) {
            ans.add(0);
        }

        // Iterate through the rest of the array
        for (int i = p.length(); i < s.length(); i++) {
            int l = sc[i - p.length()];
            int r = sc[i];

            sum = sum - Math.abs(diff[l]) - Math.abs(diff[r]);

            diff[l]--;
            diff[r]++;

            sum = sum + Math.abs(diff[l]) + Math.abs(diff[r]);

            if (sum == 0) {
                ans.add(i - p.length() + 1);
            }
        }

        return ans;
    }
}

// O(256*n)
public class Solution {
    /*
     * @param s: a string
     * @param p: a string
     * @return: a list of index
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        if (s == null || s.length() == 0 || p == null || p.length() == 0) {
            return ans;
        }

        if (s.length() < p.length()) {
            return ans;
        }

        char[] sc = s.toCharArray();
        char[] pc = p.toCharArray();

        int[] sMap = new int[256];
        int[] pMap = new int[256];

        // Initial map
        for (int i = 0; i < p.length(); i++) {
            sMap[sc[i]]++;
            pMap[pc[i]]++;
        }
        if (compare(sMap, pMap)) {
            ans.add(0);
        }

        // Sliding window
        for (int i = p.length(); i < s.length(); i++) {
            // remove left
            sMap[sc[i - p.length()]]--;
            // add right
            sMap[sc[i]]++;
            // compare sMap with pMap
            if (compare(sMap, pMap)) {
                ans.add(i - p.length() + 1);
            }
        }

        return ans;
    }

    private boolean compare(int[] sMap, int[] pMap) {
        for (int i = 0; i < 256; i++) {
            if (sMap[i] != pMap[i]) {
                return false;
            }
        }
        return true;
    }
}