如何获取所有可能的子串组合？

问题描述：

我有一个如下结构的字符串： A1（N1，N2，N3）P4（O3，O5）Y1。如何获取所有可能的子串组合？

如何获取所有组合？规则是括号内的选项不应该放在一起。对于这个例子，输出应该是：

A1N1P4O3Y1, 
A1N2P4O3Y1, 
A1N3P4O3Y1, 
A1N1P4O5Y1, 
A1N2P4O5Y1, 
A1N3P4O5Y1.

可以有括号，但它可以没有它。又如：

N3P5（L1，L2）Q1，输出应该是：

N3P5L1Q1, 
N3P5L2Q1.

与优雅的解决方案的任何人？

打破你的问题成碎片。找出如何读取输入并使用列表清单进行建模。找出如何处理所有输出中的列表清单。 –

Maroun，我需要这真的很快，我知道我可以在几个小时内完成，但我有3天的生产，这就是为什么我要求一个解决方案...谢谢无论如何... –

@DjordjeIvanovic堆栈溢出不是免费编程的来源，当你没有时间自己做。将作业卸载到本网站不合适或不被允许 –

答

主要想法是将字符串输入转换为一个包含部分的StringTemplate，该部分可以是单个字符串或一组字符串。

对于每个零件，都会创建一个迭代器。虽然某些迭代器可以继续，但更新一个保存当前部分值的字符串数组，并重置所有更改部分之前的部分迭代器。随意清除重复代码，并根据需要添加嵌套组支持和语法验证。

private static StringTemplate parse(String string) { 

    List<StringPart> parts = new ArrayList<StringPart>(); 

    boolean insideGroup = false; 
    StringBuilder currentToken = new StringBuilder(); 

    List<LiteralPart> groupParts = new ArrayList<LiteralPart>(); 

    for (int i = 0; i < string.length(); i++) { 
     char ch = string.charAt(i); 

     if (ch == '(') { 

      if (currentToken.length() != 0) { 
       parts.add(new LiteralPart(currentToken.toString())); 
       currentToken.delete(0, currentToken.length()); 
      } 

      insideGroup = true; 

     } else if (ch == ')') { 

      if (insideGroup) { 

       if (currentToken.length() != 0) { 
        groupParts.add(new LiteralPart(currentToken.toString())); 
        currentToken.delete(0, currentToken.length()); 
       } 

       parts.add(new CompositePart(groupParts)); 
       groupParts.clear(); 
       insideGroup = false; 

      } else { 
       currentToken.append(ch); 
      } 

     } else if (ch == ',') { 

      if (insideGroup) { 

       if (currentToken.length() != 0) { 
        groupParts.add(new LiteralPart(currentToken.toString())); 
        currentToken.delete(0, currentToken.length()); 
       } 

      } else { 
       currentToken.append(ch); 
      } 

     } else { 
      currentToken.append(ch); 
     } 
    } 

    if (currentToken.length() != 0) { 
     parts.add(new LiteralPart(currentToken.toString())); 
     currentToken.delete(0, currentToken.length()); 
    } 

    return new StringTemplate(parts); 

} 

private static final class StringTemplate { 

    private final List<StringPart> parts; 

    public StringTemplate(List<StringPart> parts) { 
     this.parts = parts; 
    } 

    public List<String> getCombinations() { 
     List<Iterator<String>> iterators = new ArrayList<Iterator<String>>(parts.size()); 

     for (StringPart part : parts) { 
      iterators.add(part.getStrings().iterator()); 
     } 

     String[] toJoin = new String[iterators.size()]; 

     List<String> combinations = new ArrayList<String>(); 
     int iteratorThatAdvanced; 
     int maxIteratorThatAdvanced = Integer.MIN_VALUE; 
     boolean first = true; 

     for (;;) { 

      iteratorThatAdvanced = -1; 

      for (int i = 0; i < iterators.size(); i++) { 
       Iterator<String> iterator = iterators.get(i); 

       if (first || iterator.hasNext()) { 
        String value = iterator.next(); 
        toJoin[i] = value; 

        iteratorThatAdvanced = i; 

        if (!first && i >= maxIteratorThatAdvanced) { 
         maxIteratorThatAdvanced = i; 
         break; 
        } 
       } 
      } 

      if (iteratorThatAdvanced < 0) { 
       break; 
      } 

      if (!first) { 
       for (int i = 0; i < iteratorThatAdvanced; i++) { 
        Iterator<String> iterator = parts.get(i).getStrings().iterator(); 
        iterators.set(i, iterator); 
        toJoin[i] = iterator.next(); 
       } 
      } 

      combinations.add(join(toJoin)); 
      first = false; 

     } 

     return combinations; 
    } 

} 

private static String join(String[] strings) { 
    StringBuilder builder = new StringBuilder(); 
    for (String string : strings) { 
     builder.append(string); 
    } 
    return builder.toString(); 
} 

private static abstract class StringPart { 

    abstract List<String> getStrings(); 

} 

private static final class LiteralPart extends StringPart { 

    private final String literal; 

    public LiteralPart(String literal) { 
     this.literal = literal; 
    } 

    @Override 
    List<String> getStrings() { 
     return Collections.singletonList(literal); 
    } 

} 

private static final class CompositePart extends StringPart { 

    private final List<LiteralPart> parts; 

    public CompositePart(List<LiteralPart> parts) { 
     this.parts = new ArrayList<LiteralPart>(parts); 
    } 

    @Override 
    List<String> getStrings() { 
     List<String> strings = new ArrayList<String>(parts.size()); 

     for (LiteralPart part : parts) { 
      strings.add(part.literal); 
     } 

     return strings; 
    } 

}

例子：

public static void main(String[] args) { 
    StringTemplate template = parse("A1(N1,N2,N3)P4(O3,O5)Y1"); 

    for (String combination : template.getCombinations()) { 
     System.out.println(combination); 
    } 

    template = parse("N3P5(L1,L2)Q1"); 

    for (String combination : template.getCombinations()) { 
     System.out.println(combination); 
    } 
}

如何获取所有可能的子串组合？

相关推荐