amazon find substrings

Posted on | Edited on | Views:

DFS, Time out

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

import java.util.*;

class SubString {

    static List<String> findSubStrings(String input) {
        List<String> tmp = new ArrayList<>();
        List<String> res = new ArrayList<>();
        HashSet<Character> set = new HashSet<>();

        HashMap<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < input.length(); i++) {
            map.put(input.charAt(i), i);
        }
        DFS(input, tmp, res, 0, set, map);
        return res;
    }

    static void DFS(String s, List<String> tmp, List<String> res, int index, HashSet<Character> set,
            HashMap<Character, Integer> map) {
        if (s.length() - index + tmp.size() < res.size()) {
            return;
        }

        if (index == s.length()) {
            if (res.size() < tmp.size()) {
                res.clear();
                res.addAll(tmp);

            } else if (res.size() == tmp.size()) {
                if (getLen(res) > getLen(tmp)) {
                    res.clear();
                    res.addAll(tmp);
                }
            }
            return;
        }

        if (set.contains(s.charAt(index))) {
            DFS(s, tmp, res, index + 1, set, map);
            return;
        }

        Character x = s.charAt(index);
        int y = findNext(x, s, index, set, map);
        if (y != -1) {
            tmp.add(s.substring(index, y + 1));
            DFS(s, tmp, res, y + 1, set, map);
            tmp.remove(tmp.size() - 1);
        }

        set.add(x);
        DFS(s, tmp, res, index + 1, set, map);
        set.remove(x);
    }

    static int findNext(Character x, String s, int i, HashSet<Character> set, HashMap<Character, Integer> map) {
        int res = i;
        int xx = map.get(x);
        while (res < s.length() && res < xx) {
            if (set.contains(s.charAt(res))) {
                res = -1;
                break;
            }
            xx = Math.max(xx, map.get(s.charAt(res)));
            res++;
        }
        return res;
    }

    static int getLen(List<String> res) {
        int x = 0;
        for (int i = 0; i < res.size(); i++) {
            x += res.get(i).length();
        }
        return x;
    }
}

public class MyClass {
    public static void main(String[] args) {
        String s1 = "baddacxb";
        System.err.println("original string: " + s1);
        System.out.println(SubString.findSubStrings(s1));
        // String s2="bbeadcxede";
        // System.out.println(SubString.findSubStrings(s2));
    }
}

0%