import java.io.*; import java.util.*; /** * LongestCommonSubsequence is a progra

Question

import java.io.*;
import java.util.*;

/**
* LongestCommonSubsequence is a program that will determine the longest string that is
* a subsequence of two input strings. This program applies a brute force solution technique.
*
* @author Charles Hoot
* @version 4.0
*/
public class LongestCommonSubsequence {

public static void main(String args[]) {
BagInterface<String> toCheckContainer = null;

Scanner input;
input = new Scanner(System.in);

System.out.println("This program determines the longest string that is a subsequence of two input string.");
System.out.println("Please enter the first string:");
String first = input.next();

System.out.println("Please enter the second string:");
String second = input.next();

// ADD CODE HERE TO CREATE THE BAG WITH THE INITIAL STRING
  
  
System.out.println("The strings to check are: " + toCheckContainer);
String bestSubsequence = new String("");

// ADD CODE HERE TO CHECK THE STRINGS IN THE BAG
System.out.println("Found " + bestSubsequence + " for the longest common subsequence");

}

/**
* Determine if one string is a subsequence of the other.
*
* @param check See if this is a subsequence of the other argument.
* @param other The string to check against.
* @return A boolean if check is a subsequence of other.
*/
public static boolean isSubsequence(String check, String against) {
boolean result = false;

// ADD CODE HERE TO CHECK IF WE HAVE A SUBSEQUENCE
  
  
return result;
}
}

Explanation / Answer

As Bag INterface is not provided so I couldn'ta ttempt it,

But here is major crux of code which you might be needing.

/**
* Determine if one string is a subsequence of the other.
*
* @param check See if this is a subsequence of the other argument.
* @param other The string to check against.
* @return A boolean if check is a subsequence of other.
*/
public static boolean isSubsequence(String check, String against) {
if (check.length() == 0) return true;
if (against.length() == 0) return false;

// If last characters of two strings are matching
if (check.charAt(check.length()-1) == against.charAt(against.length() - 1))
return isSubsequence(check.substring(0, check.length()-1), against.substring(0, check.length()-1));

// If last characters are not matching
return isSubsequence(check, against.substring(0, check.length()-1));
  
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.