通过迭代按字母顺序排列字符串

Question

我想我已经设法找到按字母顺序排列字符串（ABCDE 以任何顺序）的最小移动量。

有一些必须遵守的条件：

交换第一个和第二个元素 (b)，或者：
将字符串右移一位 (s)

但是，我也在尝试打印出我用来到达最短路径的移动。
例如，如果我输入 BECAD 我会得到 Minimum step used: 7 但我也想打印 bsssbsb.

现在我的 StringBuilder 一直在追加所有可能的动作。任何帮助，将不胜感激。

  public static void main(String[] args) {
        String s = "BECAD";
        int step = 0;
        System.out.println("Minimum step used: " + robot(s, step));
    }

    public static int robot(String s, int step) {

        StringBuilder sb1 = new StringBuilder();
        Queue<State> leftQ = new LinkedList<>();
        Queue<State> rightQ = new LinkedList<>();
        State nodeLeft = new State(s, step, 0, sb1);
        State nodeRight = new State(s, step, 0, sb1);
//while we havent reached ABCDE continue until one of them reaches
        while(!(nodeLeft.s.equals("ABCDE")) && !(nodeRight.s.equals("ABCDE"))) {
// first loop we will always enter the first condition.
            if(nodeLeft.previousMove == 0 || nodeRight.previousMove == 0) {
                leftQ.offer(new State(nodeLeft.s.substring(1, 2) + nodeLeft.s.substring(0, 1) + nodeLeft.s.substring(2, 5), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 1, nodeLeft.allMoves.append("b")));
                rightQ.offer(new State(nodeLeft.s.substring(4, 5) + nodeLeft.s.substring(0, 4), nodeRight.currentSteps + 1, nodeRight.previousMove + 2, nodeRight.allMoves.append("s"))); 
// there are two queues, left and right. first we swap the 1st element with the 2nd element and push it to the leftQ. The other one be will shift the string one step left and push it to the rightQ.
            } else if(nodeLeft.previousMove == 1 || nodeRight.previousMove == 1) {
                leftQ.offer(new State(nodeLeft.s.substring(4, 5) + nodeLeft.s.substring(0, 4), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 2, nodeLeft.allMoves.append("s")));
                rightQ.offer(new State(nodeRight.s.substring(4, 5) + nodeRight.s.substring(0, 4), nodeRight.currentSteps + 1, nodeRight.previousMove = 2, nodeRight.allMoves.append("s")));
            } else if(nodeLeft.previousMove == 2 || nodeRight.previousMove == 2) {
                leftQ.offer(new State(nodeLeft.s.substring(1, 2) + nodeLeft.s.substring(0, 1) + nodeLeft.s.substring(2, 5), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 1, nodeLeft.allMoves.append("b")));
                leftQ.offer(new State(nodeLeft.s.substring(4, 5) + nodeLeft.s.substring(0, 4), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 2, nodeLeft.allMoves.append("s")));
                rightQ.offer(new State(nodeRight.s.substring(1, 2) + nodeRight.s.substring(0, 1) + nodeRight.s.substring(2, 5), nodeRight.currentSteps + 1, nodeRight.previousMove = 1, nodeRight.allMoves.append("b")));
                rightQ.offer(new State(nodeRight.s.substring(4, 5) + nodeRight.s.substring(0, 4), nodeRight.currentSteps + 1, nodeRight.previousMove = 2, nodeRight.allMoves.append("s")));
// to avoid endless loop i check the previous move. If i swapped previously i must shift one step left.
            }
            nodeLeft = leftQ.poll();
            nodeRight = rightQ.poll();
// i continue to poll from both the queues to see which one reaches ABCDE first. 
// Since i am building something like a binary tree on the width
// eventually one of the nodes will reach first. Then i set the other to a max value since it never finished it search.
        }

        if(!(nodeLeft.s.equals("ABCDE"))) {
            nodeLeft.currentSteps = Integer.MAX_VALUE;
        }
        if(!(nodeRight.s.equals("ABCDE"))) {
            nodeRight.currentSteps = Integer.MAX_VALUE;
        }
        return  Math.min(nodeLeft.currentSteps, nodeRight.currentSteps);
// here i return the minimum amount of steps taken to achieve my goal
    }


public class State {

    public String s;
    public int currentSteps;
    public int previousMove;
    public StringBuilder allMoves;

    public State(String s, int currentSteps, int previousMove, StringBuilder allMoves) {
        this.s = s;
        this.currentSteps = currentSteps;
        this.previousMove = previousMove;
        this.allMoves = allMoves;
    }

}

Answer 1

您的代码有两个主要问题让您很伤心。

首先，您将相同的字符串生成器传递给左右节点。这意味着发生在左节点上的任何追加操作也发生在右节点上。

StringBuilder sb1 = new StringBuilder();
Queue<State> leftQ = new LinkedList<>();
Queue<State> rightQ = new LinkedList<>();
State nodeLeft = new State(s, step, 0, sb1);
State nodeRight = new State(s, step, 0, sb1);

这是一个简单的修复，您只需要创建两个 StringBuilder，例如

StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
State nodeLeft = new State(s, step, 0, sb1);
State nodeRight = new State(s, step, 0, sb2);

第二个问题是，对于每个节点，您实际上在第二个 else if 块中两次附加到同一个 Stringbuilder

leftQ.offer(new State(nodeLeft.s.substring(1, 2) + nodeLeft.s.substring(0, 1) + nodeLeft.s.substring(2, 5), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 1, nodeLeft.allMoves.append("b")));
leftQ.offer(new State(nodeLeft.s.substring(4, 5) + nodeLeft.s.substring(0, 4), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 2, nodeLeft.allMoves.append("s")));

rightQ.offer(new State(nodeRight.s.substring(1, 2) + nodeRight.s.substring(0, 1) + nodeRight.s.substring(2, 5), nodeRight.currentSteps + 1, nodeRight.previousMove = 1, nodeRight.allMoves.append("b")));
rightQ.offer(new State(nodeRight.s.substring(4, 5) + nodeRight.s.substring(0, 4), nodeRight.currentSteps + 1, nodeRight.previousMove = 2, nodeRight.allMoves.append("s")));

一种快速解决方法是为您创建的其中一个节点创建一个 StringBuilder，然后将现有节点传递给另一个节点，例如

leftQ.offer(new State(nodeLeft.s.substring(1, 2) + nodeLeft.s.substring(0, 1) + nodeLeft.s.substring(2, 5), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 1, new StringBuilder(nodeLeft.allMoves).append("b")));
leftQ.offer(new State(nodeLeft.s.substring(4, 5) + nodeLeft.s.substring(0, 4), nodeLeft.currentSteps + 1, nodeLeft.previousMove = 2, nodeLeft.allMoves.append("s")));

通过迭代按字母顺序排列字符串

Arranging a string alphabetically by iteration

java

sorting

string

recursion

minimum