Welcome to Subscribe On Youtube

1087. Brace Expansion

Description

You are given a string s representing a list of words. Each letter in the word has one or more options.

• If there is one option, the letter is represented as is.
• If there is more than one option, then curly braces delimit the options. For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, if s = "a{b,c}", the first character is always 'a', but the second character can be 'b' or 'c'. The original list is ["ab", "ac"].

Return all words that can be formed in this manner, sorted in lexicographical order.

 

Example 1:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:

Input: s = "abcd"
Output: ["abcd"]

 

Constraints:

• 1 <= s.length <= 50
• s consists of curly brackets '{}', commas ',', and lowercase English letters.
• s is guaranteed to be a valid input.
• There are no nested curly brackets.
• All characters inside a pair of consecutive opening and ending curly brackets are different.

Solutions

• Java
• Python

• class Solution {
      private List<String> ans;
      private List<String[]> items;
  
      public String[] expand(String s) {
          ans = new ArrayList<>();
          items = new ArrayList<>();
          convert(s);
          dfs(0, new ArrayList<>());
          Collections.sort(ans);
          return ans.toArray(new String[0]);
      }
  
      private void convert(String s) {
          if ("".equals(s)) {
              return;
          }
          if (s.charAt(0) == '{') {
              int j = s.indexOf("}");
              items.add(s.substring(1, j).split(","));
              convert(s.substring(j + 1));
          } else {
              int j = s.indexOf("{");
              if (j != -1) {
                  items.add(s.substring(0, j).split(","));
                  convert(s.substring(j));
              } else {
                  items.add(s.split(","));
              }
          }
      }
  
      private void dfs(int i, List<String> t) {
          if (i == items.size()) {
              ans.add(String.join("", t));
              return;
          }
          for (String c : items.get(i)) {
              t.add(c);
              dfs(i + 1, t);
              t.remove(t.size() - 1);
          }
      }
  }
  

• class Solution:
      def expand(self, s: str) -> List[str]:
          def convert(s):
              if not s:
                  return
              if s[0] == '{':
                  j = s.find('}')
                  items.append(s[1:j].split(','))
                  convert(s[j + 1 :])
              else:
                  j = s.find('{')
                  if j != -1:
                      items.append(s[:j].split(','))
                      convert(s[j:])
                  else:
                      items.append(s.split(','))
  
          def dfs(i, t):
              if i == len(items):
                  ans.append(''.join(t))
                  return
              for c in items[i]:
                  t.append(c)
                  dfs(i + 1, t)
                  t.pop()
  
          items = []
          convert(s)
          ans = []
          dfs(0, [])
          ans.sort()
          return ans
  
  

All Problems

All Solutions