Question

JAVA Recursion: For this assignment, you will be working with various methods to manipulate strings using recursion. The method signatures are included in the starter code below, with a more detailed explanation of what function the method should perform. You will be writing the following methods:

• stringClean()
• palindromeChecker()
• reverseString()
• totalWord()
• permutation()

You will be using tools in the String class like .substring(), .charAt(), and .length() in all of these methods, so be careful with indices. If you get stuck, think about the base case of the method, then what needs to be done in the recursive case.

Do not use a loop in any of the methods except permutationHelper(). You may use a loop in permutationHelper() but there should be a recursive call in the method.

Include your own testing in main after instantiating an object of the class to check that your methods are working as expected.

For more recursion practice (or any other subject practice with Java), visit Coding Bat for some great problems to test your skills.

public class Main {

public static void main(String[] args) {

}


/* stringClean()
* Given a string, return recursively a "cleaned" string
* where adjacent chars that are the same have been reduced
* to a single char. So "yyzzza" yields "yza".
*/
public String stringClean(String str){
}


/* palindromeChecker()
* Given a string, check if it is a palindrome recursively.
* Return true if the given word is a palindrome, and false if it is not.
* For example, "abcba" would yield true, but "abc" would not.
* A word is a palindrome if the letters in the word are symmetric.
*/
public boolean palindromeChecker(String word){
  
}


/* reverseString()
* Given a string, recursively reverse the letters to yield a new string.
* For example, if given "abcde", the method would yield "edcba".
*/
public String reverseString(String word){
  
}

/* totalWord()
* Given a string, recursively find the sum of the integer values of the characters in the word.
* Since characters have corresponding integer values from the ASCII table, you are able to sum them into a single integer.
* For example, if given "abc", the method would return 294.
*/
public int totalWord(String word){

}

/*
* The following method is given to you, and you will be responsible for completing the permutationHelper method it calls.
* Sometimes, helper methods are used for recursive methods when another parameter is needed to recursively call a method repeatedly, but passing that parameter initially doesn't make sense.
*/
public String permutation(String word){
return permutationHelper(" ", word);
}

/* permutationHelper()
* This method is called by the permutation method.
* Given a string, return a string that lists all possible permutations of the letters in the string, with spaces preceding each permutation.
* For example, "123" would give " 123 132 213 231 312 321".
* The perm parameter keeps track of the current permutation you are creating.
* Consider using the a for loop to call the method recursively a certain number of times with different parameters, so you cover all permutations.
*/
public String permutationHelper(String perm, String word) {
}
  

}

Answer 1

Here are the required methods with the driver main(). I have kept some inline comments to help explain the logic. Still, if there is something that is not very clear, do let me know and I will be glad to assist you back.

package myStore;

public class StringCode {

   /* stringClean()
   * Given a string, return recursively a "cleaned" string
   * where adjacent chars that are the same have been reduced
   * to a single char. So "yyzzza" yields "yza".
   */
   public static String stringClean(String str){      
       // base case, where the string is made of only 1 character
       if (str.length()==1)
           return str;
       // In any other case, we need to see if the first character is equal to
       // the next character or not, in the later case, we need to recurse the
       // method with the new substring of the original word. In the former case,
       // we should just ignore the character and move on with adding it only once
       // in the final string.
        if (str.charAt(0) != str.charAt(1))
            return str.charAt(0) + stringClean(str.substring(1));      
        return stringClean(str.substring(1));
   }

   /* palindromeChecker()
   * Given a string, check if it is a palindrome recursively.
   * Return true if the given word is a palindrome, and false if it is not.
   * For example, "abcba" would yield true, but "abc" would not.
   * A word is a palindrome if the letters in the word are symmetric.
   */
   public static boolean palindromeChecker(String word){
       // Base case: string is of length 0 or 1, it's a palindrome, so return true.
        if(word.length() == 0 || word.length() == 1)
            return true;       
        /*
         * Start with the first and last characters of the string.
         * If they match, keep on checking the same by matching the next character
         * with the second last character until the middle of the string is found.
         * Any failure found will make the string non-palindrome.
         */
        if(word.charAt(0) == word.charAt(word.length()-1))
           // .substring() will keep on making the small substrings out of the original string
           return palindromeChecker(word.substring(1, word.length()-1));
        return false;
   }

   /* reverseString()
   * Given a string, recursively reverse the letters to yield a new string.
   * For example, if given "abcde", the method would yield "edcba".
   */
   public static String reverseString(String word){
       /*
       * Return the entire word if it's empty as there is no need to reverse.
       */
       if (word.length() == 0)
             return word;
       // Start appending the first character of the string at the end of the new string
       // and recurse the new substring after cutting the first character out of it.
       return reverseString(word.substring(1)) + word.charAt(0);
   }

   /* totalWord()
   * Given a string, recursively find the sum of the integer values of the characters in the word.
   * Since characters have corresponding integer values from the ASCII table, you are able to sum
   * them into a single integer.
   * For example, if given "abc", the method would return 294.
   */
   public static int totalWord(String word){
       /*
       * Base case: when the string is of 1 character only, just return the ASCII value
       * of that character
       */
       if (word.length() == 1)
           return (int)word.charAt(0);
       /*
       * Else, we need to keep adding the ASCII value of first character with the
       * recursed value of the substring found by cutting the first character of the
       * original string.
       */
       return (int)word.charAt(0) + totalWord(word.substring(1, word.length()));
   }

   /*
   * The following method is given to you, and you will be responsible for completing the
   * permutationHelper method it calls. Sometimes, helper methods are used for recursive methods
   * when another parameter is needed to recursively call a method repeatedly, but passing that
   * parameter initially doesn't make sense.
   */
   public static String permutation(String word){
       return permutationHelper(" ", word);
   }

   /* permutationHelper()
   * This method is called by the permutation method.
   * Given a string, return a string that lists all possible permutations of the letters in the
   * string, with spaces preceding each permutation.
   * For example, "123" would give " 123 132 213 231 312 321".
   * The perm parameter keeps track of the current permutation you are creating.
   * Consider using the a for loop to call the method recursively a certain number of times with
   * different parameters, so you cover all permutations.
   */
   public static String permutationHelper(String perm, String word) {
       /*
       * Base case: If the word is empty, just print the delimiter along with the word.
       */
        if (word.length()==0) System.out.print(perm + word);
        /*
         * Otherwise, as instructed, using a for loop to keep getting the permutations.
         * For example, in first iteration, we get the .charAt(0) that is 1 (support the
         * string is "123") appended with "23" (found by word.substring(i+1, word.length()))
         * This goes on until we are left with only no characters in the string.
         */
        for (int i = 0; i < word.length(); i++) {
              permutationHelper(perm + word.charAt(i), word.substring(0,i) + word.substring(i+1, word.length()));
        }
       return "";
   }
  
   // Driver code main()
   public static void main(String[] args) {
       System.out.println(stringClean("aabbbbbbccdbbxrr"));
       System.out.println(palindromeChecker("abcdcbaa"));
       System.out.println(reverseString("reverse me"));
       System.out.println(totalWord("abc"));
       System.out.println(permutation("123"));
   }
}

IDE and Execution screenshot :

StringCode StringCode.java X myStore ▸ src myStore ▸ 1 package myStore; 3 public class StringCode { HNM to /* stringClean() * Given a string, return recursively a "cleaned" string * where adjacent chars that are the same have been reduced * to a single char. So "yxzzza" yields "yza. 9999 public static String stringclean(String str){ // base case, where the string is made of only 1 character if (str.length() ==1) return str; // In any other case, we need to see if the first character is equal to // the next character or not, in the later case, we need to recurse the od with the new substring of the original word. In the former case, // we should just ignore the character and move on with adding it only once // in the final string if (str.charAt(0) != str.charAt(1)) return str.charAt(0) + stringClean(str.substring(1)); return stringClean(str.substring(1)); 26 /* palindromeChecker() * Given a string, check if it is a palindrome recursively. * Return true if the given word is a palindrome, and false if it is not. * For example, "abcba" would yield true, but "abc" would not. * A word is a palindrome if the letters in the word are symmetric. public static boolean palindromeChecker (String word) { // Base case: string is of length or 1, it's a palindrome, so return true. if(word. length() == 0 || word.length() == 1) return true; /* * Start with the first and last characters of the string. * If they match, keep on checking the same by matching the next character * with the second last character until the middle of the string is found. * Any failure found will make the string non-palindrome. */ if(word.charAt() == word.charAt(word.length()-1)) // .substring() will keep on making the small substrings out of the original string return palindromeChecker(word.substring(1, word. length()-1)); return false; 480 49 50 /* reverseString * Given a string, recursively reverse the letters to yield a new string. * For example, if given "abcde", the method would yield "edcba". 51 public static String reverseString(String word) { * Return the entire word if it's empty as there is no need to reverse. * / if (word. length() == 0) return word; // Start appending the first character of the string at the end of the new string // and recurse the new substring after cutting the first character out of it. return reverseString(word.substring(1)) + word.charAt(0);

StringCode.java X myStore ▸ s rc #myStore ▸ StringCode permutationHelper(String, String): String 61 } 62 630 /* totalWord) * Given a string, recursively find the sum of the integer values of the characters in the word. * Since characters have corresponding integer values from the ASCII table, you are able to sum 66 * them into a single integer. * For example, if given "abc", the method would return 294. 690 public static int totalword(String word){ 65 70 71 72 * Base case: when the string is of 1 character only, just return the ASCII value * of that character */ if (word. length() == 1) return (int) word.charAt(0); * Else, we need to keep adding the ASCII value of first character with the * recursed value of the substring found by cutting the first character of the * original string. return (int)word.charAt(0) + totalWord(word.substring(1, word.length())); 840 85 86 * The following method is given to you, and you will be responsible for completing the * permutationHelper method it calls. Sometimes, helper methods are used for recursive methods * when another parameter is needed to recursively call a method repeatedly, but passing that * parameter initially doesn't make sense. 87 900 public static String permutation(String word) { return permutationHelper(" ", word); 93 940 98 /* permutationHelper) * This method is called by the permutation method. * Given a string, return a string that lists all possible permutations of the letters in the * string, with spaces preceding each permutation. * For example, "123" would give " 123 132 213 231 312 321". * The perm parameter keeps track of the current permutation you are creating. * Consider using the a for loop to call the method recursively a certain number of times with * different parameters, so you cover all permutations. 100 101 102 1030 104 105 106 0107 108 public static String permutationHelper (String perm, String word) 1 * Base case: If the word is empty, just print the delimiter along with the word. if (word. length() ==0) System.out.print(perm + word); * Otherwise, as instructed, using a for loop to keep getting the permutations. * For example, in first iteration, we get the .charAt(0) that is 1 (support the * string is "123") appended with "23" (found by word.substring(i+1, word. length)) * This goes on until we are left with only no characters in the string. о со уол еш мноо for (int i = 0; i < word.length(); i++) { permutationHelper (perm + word.charAt(i), word.substring(0, i) + word.substring(i+1, word.length()); return ""; L118 119