Skip to content

1087. Brace Expansion 👍

  • Time: $O(2^n)$
  • Space: $O(2^n)$
 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
class Solution {
 public:
  vector<string> expand(string s) {
    vector<string> ans;
    string path;
    dfs(s, 0, path, ans);
    return ans;
  }

 private:
  void dfs(const string& s, int i, string& path, vector<string>& ans) {
    if (i == s.length()) {
      ans.push_back(path);
      return;
    }
    if (s[i] == '{') {
      const int nextRightBraceIndex = s.find_first_of('}', i);
      for (const char c :
           split(s.substr(i + 1, nextRightBraceIndex - i - 1), ',')) {
        path.push_back(c);
        dfs(s, nextRightBraceIndex + 1, path, ans);
        path.pop_back();
      }
    } else {  // s[i] != '{'
      path.push_back(s[i]);
      dfs(s, i + 1, path, ans);
      path.pop_back();
    }
  }

  vector<char> split(const string& s, char delimiter) {
    vector<char> splitted;
    for (const char c : s)
      if (c != delimiter)
        splitted.push_back(c);
    return splitted;
  }
};

 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
class Solution {
  public String[] expand(String s) {
    List<String> ans = new ArrayList<>();

    dfs(s, 0, new StringBuilder(), ans);
    Collections.sort(ans);
    return ans.toArray(new String[0]);
  }

  private void dfs(final String s, int i, StringBuilder sb, List<String> ans) {
    if (i == s.length()) {
      ans.add(sb.toString());
      return;
    }
    if (s.charAt(i) == '{') {
      final int nextRightBraceIndex = s.indexOf("}", i);
      for (final String c : s.substring(i + 1, nextRightBraceIndex).split(",")) {
        sb.append(c);
        dfs(s, nextRightBraceIndex + 1, sb, ans);
        sb.deleteCharAt(sb.length() - 1);
      }
    } else { // s[i] != '{'
      sb.append(s.charAt(i));
      dfs(s, i + 1, sb, ans);
      sb.deleteCharAt(sb.length() - 1);
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def expand(self, s: str) -> list[str]:
    ans = []

    def dfs(i: int, path: list[str]) -> None:
      if i == len(s):
        ans.append(''.join(path))
        return
      if s[i] == '{':
        nextRightBraceIndex = s.find('}', i)
        for c in s[i + 1:nextRightBraceIndex].split(','):
          path.append(c)
          dfs(nextRightBraceIndex + 1, path)
          path.pop()
      else:  # s[i] != '{'
        path.append(s[i])
        dfs(i + 1, path)
        path.pop()

    dfs(0, [])
    return sorted(ans)