Question

In: Computer Science

IN JAVA A recursive method that takes a String as its argument and returns a list...

IN JAVA

  • A recursive method that takes a String as its argument and returns a list of Strings which includes all anagrams of the String. This method will contain a loop that generates each possible substring consisting of all but one character in the input String, ie the substring that omits the first letter, then the substring that omits the second letter, etc. Within the loop, the method calls itself recursively for each substring. For each String in the list returned by the recursive call, add the omitted character back to the end and add the String to the list to be returned. When the first instance of this method returns, the list will contain all anagrams of the original input String. It may help to work this out with a pencil and paper for a very short string (like "abc".) The most straightforward base case (termination condition for the recursion) is to return a list containing only a new empty String if the input String has length 0. If you want a challenge, try replacing this algorithm with one that uses the only recursion, with no loops.
  • A nonrecursive method that starts the recursion for the filtering step. This method will take a list of Strings, consisting of the anagrams, as its argument. Use a loop that takes each String in the list, converts it to an array of Strings using String's split() method with a blank space as the argument, and then uses the array to provide values for a list of Strings. The result of this will be a list of Strings in which each String is a word from the anagram. Still, inside the loop, call the recursive filter method for each of these Strings. In each case when it receives a non-null String as the return value fo the recursive filter method, it will add the String to the list which it returns.
  • A recursive filter method that takes a list of Strings and returns the following:
    • if all of the Strings in the list are contained in the list of valid words, return a single String made up of the Strings in the order in which they appear in the list
    • if any of the Strings in the list do not appear in the list of valid words, return null. This should be much more common than the first case.

If a list is received for which the last String is in the word list, this method should recursively call itself on a list consisting of all but the last word. If the recursive call returns a String (not null), add the last word back to the end of the String and return it. This method should not contain any loops.

Solutions

Expert Solution

Answer of the first part
Save the program in file Main.java

import java.util.HashSet;
import java.util.Set;

public class Main {
// function to create permutation of the given string
public static Set<String> generate_permutation(String inputStr){
Set<String> set = new HashSet<String>();
if (inputStr.length() == 0)
return set;

Character chr = inputStr.charAt(0);
if (inputStr.length() > 1) {
inputStr = inputStr.substring(1);
Set<String> pSet = generate_permutation(inputStr);
for (String x : pSet) {
for (int i = 0; i <= x.length(); i++) {
set.add(x.substring(0, i) + chr + x.substring(i));
}
}
} else {
set.add(chr + "");
}
return set;
}

// The main function
public static void main(String[] args) {
System.out.println(generate_permutation("abc"));
}

}

Compile the file as

$javac Main.java

Execute the file as
java Main

to get the output as below

[bca, acb, abc, cba, bac, cab]



Related Solutions

Write a recursive method using Java that takes a string s as input and returns a...
Write a recursive method using Java that takes a string s as input and returns a list that contains all the anagrams of the string s. An anagram is a word formed by rearranging the letters of a different word. For instance, the word ‘cat’ is an anagram of ‘act’. Notice that the output list cannot contain duplicates.
Code in Java Write a recursive method, reverseString, that accepts a String and returns the String...
Code in Java Write a recursive method, reverseString, that accepts a String and returns the String reversed. Write a recursive method, reverseArrayList, that accepts an ArrayList of Strings and returns the ArrayList in reserve order in reserve order of the input ArrayList. Write a main method that asks the user for a series of Strings, until the user enters “Done” and puts them in an ArrayList. Main should make use to reverseArrayList and reverseString to reverse each String in the...
In Java, write a recursive function that accepts a string as its argument and prints the...
In Java, write a recursive function that accepts a string as its argument and prints the string in reverse order. Demonstrate the function in a driver program.
Java RECURSIVE methods: => intersection(String s1, String s2): takes two strings and returns the string consisting...
Java RECURSIVE methods: => intersection(String s1, String s2): takes two strings and returns the string consisting of all letters that appear in both s1 and s2. => union(String s1, String s2): takes two strings and returns the string consisting of all letters that appear in either s1 or s2. =>difference(String s1, String s2): takes two strings and returns the string consisting of all letters that appear only in s1.
java/netbeans Write a recursive method, reverseString, that accepts a String and returns the String reversed. Write...
java/netbeans Write a recursive method, reverseString, that accepts a String and returns the String reversed. Write a recursive method, reverseArrayList, that accepts an ArrayList of Strings and returns an ArrayList in reserve order of the input ArrayList. Write a main method that asks the user for a series of Strings, until the user enters “Done” and puts them in an ArrayList. Main should make use to reverseArrayList and reverseString to reverse each String in the ArrayList and then reverse the...
Write a java method that takes a string and returns an array of int that contains...
Write a java method that takes a string and returns an array of int that contains the corresponding alphabetic order of each letter in the received string: An illustration: the method takes: "Sara" the method returns: {4,1,3,2} another illustration: the method takes: "hey" the method returns: {2,1,3}
write a recursive method that returns the product of all elements in java linked list
write a recursive method that returns the product of all elements in java linked list
JAVA Arrays 4 Write a method called isPalindrome that takes a String as input and returns...
JAVA Arrays 4 Write a method called isPalindrome that takes a String as input and returns true if the String is a palindrome.
Java please. Write a static method sqrt()that takes a double argument and returns the square root...
Java please. Write a static method sqrt()that takes a double argument and returns the square root of that number using newton's method to compute result.
Create a Java method findLongestPalindrome that takes a Scanner scn as its parameter and returns a...
Create a Java method findLongestPalindrome that takes a Scanner scn as its parameter and returns a String. It returns the longest token from scn that is a palindrome (if one exists) or the empty string (otherwise). (Implementation note: Use the built in isPalindrome method. This method calls for an optimization loop.) Where the isPalindrome Method takes a String s as a parameter and returns a boolean. It returns true if s reads the same forwards and backwards, i.e., is a...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT