缺少此算法的一些字符串子序列

问题描述 投票:1回答:1

我希望得到以下字符串子序列模式:

# input - ALEX
# 1 - A, L, E, X
# 2 - AL, AE, AX, LE, LX, EX
# 3 - ALE, ALX, AEX, LEX
# 4 - ALEX

我写了这个,它最多,但我错过了“LX”,“AE”,“ALX”和“AEX”。我可以在没有添加第三个循环的情况下获得它

public class StringPermutations {
    public void stringPermutations(String input) {
        for(int i = 0; i<input.length();i++){
            for(int j = i; j<input.length(); j++){
                String s = input.substring(i,j+1);
                System.out.println(s);
            }
        }
    }

    public static void main(String[] args) {
        new StringPermutations().stringPermutations("ALEX");
    }
}
java subset
1个回答
4
投票

您所描述的更多是找到所有subsequences的问题。你不能通过两个嵌套for循环来实现这一点。递归求解更容易,如下所示:

// Find all subsets
public List<String> helper(String input) {
    if (input.isEmpty())
        return Collections.singletonList("");

    List<String> result = new ArrayList<>();
    List<String> subResult = helper(input.substring(1));
    result.addAll(subResult);
    for (String s : subResult)
        result.add(input.charAt(0) + s);
    return result;
}

// Print all subsets using the helper method
public void stringPermutations(String input) {
    for (String s : helper(input))
        System.out.println(s);
}

该解决方案还包括空字符串。 (不确定为什么在描述问题顶部的模式时压制了0案例;)

使用一些lambda foo,您可以打印出如下结果:

helper(input).stream()
             .collect(groupingBy(String::length, toList()))
             .entrySet()
             .stream()
             .forEach(e -> System.out.println(e.getKey() + ": " + e.getValue()));

输出:

0: []
1: [X, E, L, A]
2: [EX, LX, LE, AX, AE, AL]
3: [LEX, AEX, ALX, ALE]
4: [ALEX]
热门问题
推荐问题
最新问题