代码之家 › 专栏 › 技术社区 › crazyy_photonn

将数字串分成1位数和2位数两组

backtracking string java

-2

crazyy_photonn · 技术社区 · 6 年前

我试着把一个给定的数字串分成1位数和2位数。像这样的:

Input : 1234 Output : (1,2,34) (1,23,4) (1,2,3,4) (12,34) (12,3,4)

我一直试图用回溯法来解决这个问题,但一直未能得到完美的结果。我的尝试如下:

import java.util.Arrays;
import java.util.ArrayList;

public class MyClass {

    private static void func(ArrayList<String> res, String digits, String s){
        if(digits.length() <= 0){
            res.add(s.substring(0, s.length()-1));
            return;
        }

        String temp = digits;
        String prev_s = s;

        s = s  + digits.charAt(0) + ","; // chosen one character
        func(res, digits.substring(1), s);

        prev_s = s;

        if(digits.length() >= 2){
            s = s +  digits.substring(0,2) + ","; // chosen two characters
            func(res, digits.substring(2), s);
        }

        s = prev_s;
        digits = temp; // unchoosing
    }

    public static void main(String args[]) {

        String digits = "1234";
        ArrayList<String> res = new ArrayList<>();
        String s = "";
        func(res, digits, s);
        for(int i =0; i < res.size(); i++){
            System.out.println(res.get(i));
        }
    }       
}

我得到的答案如下:

1,2,3,4
1,2,3,34
1,2,23,4
1,12,3,4
1,12,3,34

我做错什么了?我想我在创建子字符串的时候弄错了什么地方。

另外,不使用回溯也能解决这个问题吗? 谢谢!

1 回复 | 直到 6 年前

1

2

Andreas dfa 6 年前

你的问题是恢复的任务 s 是错误的方式:

prev_s = s; –_ s = prev_s;

仅此一项就能解决你的问题。

除此之外:

你不需要最后两个陈述。他们什么也不做。
记住,java是按值传递的,所以在返回之前不需要恢复参数。
不应该更改参数的值。相反,只需在递归方法调用中进行连接。
删除 temp 和 prev_s 因为他们不再需要了。
代码可以通过预加逗号而不是后缀来稍微简化。

public class MyClass {
    private static void func(ArrayList<String> res, String digits, String s){
        if (digits.isEmpty()) {
            res.add(s.substring(1));
            return;
        }
        func(res, digits.substring(1), s + ',' + digits.charAt(0));
        if (digits.length() >= 2) {
            func(res, digits.substring(2), s + ',' + digits.substring(0, 2));
        }
    }

    public static void main(String args[]) {
        ArrayList<String> res = new ArrayList<>();
        func(res, "1234", "");
        for (String r : res) {
            System.out.println(r);
        }
    }
}

输出

1,2,3,4
1,2,34
1,23,4
12,3,4
12,34