Brace Expansion II LeetCode solution in Java

1
class Solution {
2
  // To Get the value of index traversed in a recursive call.
3
  int index = 0;
4

5
  public List<String> braceExpansionII(String expression) {
6
    List<String> result = util(0, expression);
7
    Set<String> set = new TreeSet<>();
8
    set.addAll(result);
9
    return new ArrayList<>(set);
10
  }
11

12
  List<String> util(int startIndex, String expression) {
13
    // This represents processed List in the current recursion.
14
    List<String> currentSet = new ArrayList<>();
15
    boolean isAdditive = false;
16
    String currentString = "";
17
    // This represents List that is being processed and not yet merged to currentSet.
18
    List<String> currentList = new ArrayList<>();
19

20
    for (int i = startIndex; i < expression.length(); ++i) {
21

22
      if (expression.charAt(i) == ',') {
23
        isAdditive = true;
24
        if (currentString != "" && currentList.size() == 0) {
25
          currentSet.add(currentString);
26
        } else if (currentList.size() > 0) {
27
          for (var entry : currentList) {
28
            currentSet.add(entry);
29
          }
30
        }
31

32
        currentString = "";
33
        currentList = new ArrayList<>();
34
      } else if (expression.charAt(i) >= 'a' && expression.charAt(i) <= 'z') {
35
        if (currentList.size() > 0) {
36
          List<String> tempStringList = new ArrayList<>();
37
          for (var entry : currentList) {
38
            tempStringList.add(entry + expression.charAt(i));
39
          }
40
          currentList = tempStringList;
41
        } else {
42
          currentString = currentString + expression.charAt(i);
43
        }
44
      } else if (expression.charAt(i) == '{') {
45
        List<String> list = util(i + 1, expression);
46
        // System.out.println(list);
47
        // Need to merge the returned List. It could be one of the following.
48
        // 1- ..., {a,b,c}
49
        // 2- a{a,b,c}
50
        // 3- {a,b,c}{d,e,f}
51
        // 3- {a,b,c}d
52
        if (i > startIndex && expression.charAt(i - 1) == ',') {
53
          // Case 1
54
          currentList = list;
55
        } else {
56
          if (currentList.size() > 0) {
57
            List<String> tempList = new ArrayList<>();
58
            for (var entry1 : currentList) {
59
              for (var entry2 : list) {
60
                // CASE 3
61
                tempList.add(entry1 + currentString + entry2);
62
              }
63
            }
64

65
            // System.out.println(currentList);
66
            currentList = tempList;
67
            currentString = "";
68
          } else if (currentString != "") {
69
            List<String> tempList = new ArrayList<>();
70
            for (var entry : list) {
71
              // case 2
72
              tempList.add(currentString + entry);
73
            }
74

75
            currentString = "";
76
            currentList = tempList;
77
          } else {
78
            // CASE 1
79
            currentList = list;
80
          }
81
        }
82

83
        // Increment i to end of next recursion's processing.
84
        i = index;
85
      } else if (expression.charAt(i) == '}') {
86
        if (currentString != "") {
87
          currentSet.add(currentString);
88
        }
89

90
        // {a{b,c,d}}
91
        if (currentList.size() > 0) {
92
          for (var entry : currentList) {
93

94
            currentSet.add(entry + currentString);
95
          }
96
          currentList = new ArrayList<>();
97
        }
98

99
        index = i;
100
        return new ArrayList<>(currentSet);
101
      }
102
    }
103

104
    if (currentList.size() > 0) {
105

106
      currentSet.addAll(currentList);
107
    }
108

109
    // {...}a
110
    if (currentString != "") {
111

112
      List<String> tempSet = new ArrayList<>();
113
      if (currentSet.size() > 0) {
114
        for (var entry : currentSet) {
115
          tempSet.add(entry + currentString);
116
        }
117

118
        currentSet = tempSet;
119
      } else {
120
        currentSet = new ArrayList<>();
121
        currentSet.add(currentString);
122
      }
123
    }
124

125
    return new ArrayList<>(currentSet);
126
  }
127
}