Permutations of a string using a stack in Java

Question

I am having a problem figuring out why my code wont work. The code is supposed to push a string onto a stack. then it will put a "+" sign in front of the string. (example [+dog]. Next, it pops the stack. It moves the Characters on the right side of the "+" sign to the left side in the string, one by one(ex. [d+og] [o+dg] [g+do] and push these onto the stack. this repeats over and over until all the permutations of the string end with a plus sign(example [dog+][dgo+][god+][gdo+][odg+][ogd+] it then sees if the string on the stack has a "+" sign at the end, and if it does it prints the statement out. Here is my code:

The problem i'm having is in my last else statement. I cant get the characters to move to the other side of the "+" sign.

import java.util.Scanner;
import java.util.Stack;
import java.util.*;
import java.lang.*;

public class string_Perm{

    public static void main(String[] args) {// this takes user input for a string and runs it through the program
        Scanner inputString = new Scanner(System.in);
        String userInput;
        System.out.print("Enter a String: ");
        userInput = inputString.next();
        // test print statement below
        //System.out.println(userInput);
        PermString(userInput);

    }
    public static void PermString(String userInput){
        Stack permStack = new Stack();
        permStack.push("+" + userInput);//this pushes the user input string onto the stack.                 
        // test print statement below
        //System.out.println(permStack);
        while(!permStack.isEmpty()){
            String currentItem = (permStack.pop().toString());// it then pops the top of the stack while the stack isn't empty.
            if(currentItem.endsWith("+")){
                currentItem.substring(0,currentItem.length()-1);// if the string ends with a +, you print the string without the + at the end
                System.out.println(currentItem);

            }
            else{// this else statement is where i am having trouble its supposed to split the string at the plus sign and then move each char one by one to infront of the "+" sign, then push it onto the stack.
                String[] charArray = currentItem.split("\\+");
                System.out.println(charArray[charArray.length-1]);
                for(int i = 0;i <= charArray.length; i++){
                    String getWord = charArray[charArray.length - 1];
                    String addWord = (charArray[i] + "+" + getWord.substring(0,i) + getWord.substring(i,0));
                    System.out.println(addWord);
                    permStack.push(addWord);

                }



            }



        }





    }



}

Any changes to this code or different methods are welcome. Thanks in advance.

Answer 1

You have problems with your indexes. My suggestions:

1. The for loop needs to iterate over the length of the second string in charArray (charArray holds the string not the characters!).
2. You can use a Stringbuilder to remove the character at position i instead of doing your two getWord.substring().

Here is what I suggest for the code in the for loop:

String[] charArray = currentItem.split("\\+");
for(int i = 0; i < charArray[1].length(); i++){
   String getWord = charArray[charArray.length - 1];
   StringBuilder sb = new StringBuilder(getWord);
   String addWord = (getWord.charAt(i) + charArray[0] + "+" + sb.deleteCharAt(i).toString());
   System.out.println(addWord);
   permStack.push(addWord);

}

Try this and let me know if this is what you want.