Question

1087. 花括号展开

English Version

题目描述

给定一个表示单词列表的字符串 s 。单词中的每个字母都有一个或多个选项。

• 如果有一个选项，则字母按原样表示。
• 如果有多个选项，则用大括号分隔选项。例如,  "{a,b,c}"  表示选项  ["a", "b", "c"]  。

例如，如果

  s = "a{b,c}"  ，第一个字符总是 'a' ，但第二个字符可以是 'b' 或 'c' 。原来的列表是 ["ab", "ac"] 。

请你 按字典顺序 ，返回所有以这种方式形成的单词。

 

示例 1：

输入：s = "{a,b}c{d,e}f"
输出：["acdf","acef","bcdf","bcef"]

示例 2：

输入：s = "abcd"
输出：["abcd"]

 

提示：

• 1 <= S.length <= 50
• s 由括号 '{}' , ',' 和小写英文字母组成。
• s 保证是一个有效的输入。
• 没有嵌套的大括号。
• 在一对连续的左括号和右括号内的所有字符都是不同的。

解法

方法一

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

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);
    }
  }
}