I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Longest Common Subsequence

08.29.2012
| 3852 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

Longest Common Subsequence

The LCS of two groups is the longest group that are common between both and in the same order in each group. Let's look at an example:

Group A: dzone puzzles

Group B: dropzone

The LCS here is dzone

Another example: 

Group A:  1234

Group B:  12222354

If you're still confused, there's a good explanation over at Wikipedia.

What you need to do in this challenge is write a method that identifies the LCS between two String parameters.

Catch up on all our previous puzzlers here.

Comments

Vijay Nathani replied on Thu, 2012/08/30 - 4:05am

Groovy solution

def maxSubSequence(a,b) {
	def convert = { it.toList().subsequences().collect {it.join('')} }
	def sequencesA = convert(a)
	sequencesA.retainAll(convert(b))
	sequencesA.max {it.size()}
}
println maxSubSequence('dzone puzzles','dropzone') //prints dopze

println maxSubSequence('1234','12222354') //prints 1234 

James Nute replied on Thu, 2012/08/30 - 3:27pm

Not convinced it's the most efficient way to go, but its one way to go about it in C++ 
#include <iostream>
#include <string>
using namespace std;

std::string LCS(std::string groupA, std::string groupB){

	std::string result;

	int lengthOfA = groupA.length()-1;
	int lengthOfB = groupB.length()-1;

	char endOfA = groupA[lengthOfA];
	char endOfB = groupB[lengthOfB];

	if(lengthOfA < 0 || lengthOfB < 0){
		return result;
	}

	if(endOfA==endOfB){
		result.insert(0,1,endOfA);
		result.insert(0,LCS(groupA.substr(0,lengthOfA),groupB.substr(0,lengthOfB)));
	}
	else{
		std::string lcs1(LCS(groupA.substr(0,lengthOfA+1),groupB.substr(0,lengthOfB)));
		std::string lcs2(LCS(groupA.substr(0,lengthOfA),groupB.substr(0,lengthOfB+1)));
		if(lcs1.length() > lcs2.length()){
		   result.insert(0,lcs1);
		}
		else{
		   result.insert(0,lcs2);
		}
	}
	return result;
}

int main() {
	std::string groupA("dzone puzzles");
	std::string groupB("dropzone");

	cout << "LCS is " << LCS(groupA,groupB) <<endl;
	return 0;
}

sun east replied on Thu, 2012/08/30 - 7:29pm

A short but not efficient solution written by Scala:

 

def lcs(a: String, b: String): String = {
  if(a.size > 0 && b.size > 0) {
    val pre = if(a(0) == b(0)) ""+a(0) else ""
    Seq(lcs(a,b.tail),lcs(a.tail,b),
	pre + lcs(a.tail,b.tail)).maxBy(_.size)
  }
  else ""
} 

 

Vijay Nathani replied on Thu, 2012/08/30 - 11:22pm in response to: James Nute

Awesome. Your recursive algorithm in groovy

def longerString(s1,s2) { s1.size() > s2.size()? s1 : s2 }
def lcs(a,b) {
	if (!a || !b) return ""
	(a[0] == b[0])? (a[0] + lcs(a.substring(1),b.substring(1))): longerString(lcs(a,b.substring(1)), lcs(a.substring(1),b))	
}
println lcs('dzone puzzles','dropzone') //prints dopze

println lcs('1234','122222354') //prints 1234 

Mahtab Alam replied on Wed, 2014/08/27 - 8:41am

/*
I haven`t refactored the code for words with spaces
This Program uses Dynamic Programming Approach
*/
class LCS
{

   public static void main(String args[])
   {
      System.out.print("Enter First String : ");
	  String x=System.console().readLine();
	  System.out.print("Enter Second String : ");
	  String y=System.console().readLine();
	  
	  char[]xArray=x.toCharArray();
	  char[]yArray=y.toCharArray();
	  
	  int xSize=xArray.length;
	  int ySize=yArray.length; 
	  
	  int lcs[][]=new int[xSize+1][ySize+1];
	  String marks[][]=new String[xSize][ySize];
	  
	  for(int j=0;j<=ySize;j++)
	  {
	     lcs[0][j]=0;
	  }
	  for(int i=0;i<=xSize;i++)
	  {
	    lcs[i][0]=0;
	  }
	  for(int i=1;i<=xSize;i++)
	  {
	      for(int j=1;j<=ySize;j++)
		  {
		     if(xArray[i-1]==yArray[j-1])
			 {
			   lcs[i][j]=lcs[i-1][j-1]+1;
			   marks[i-1][j-1]="D";
			 }
			 else if(lcs[i][j-1] >= lcs[i-1][j])
			 {
			   lcs[i][j]=lcs[i][j-1];
			   marks[i-1][j-1]="L";
			 }
			 else
			 {
			   lcs[i][j]=lcs[i-1][j];
			   marks[i-1][j-1]="U";
			 }
		  }
	  }
	  /* 
	  System.out.println("\nLCS Matrix is : ");
	  
	  System.out.println();
	  for(int i=0;i<=xSize;i++)
	  {
	    
	    for(int j=0;j<=ySize;j++)
		{
		  System.out.print(lcs[i][j]+"\t");
		}
		System.out.println();
	  } 
	  */
	  
	 /* System.out.println("Marks Matrix is :"); 
	  for(int i=0;i<xSize;i++)
	  {
	    for(int j=0;j<ySize;j++)
		{
		  System.out.print(marks[i][j]+"  ");
		}
		System.out.println();
	  }
	  */
	  int i=xSize-1;
      int j=ySize-1;	
      System.out.println("----------------------------------------------");
      int counter=lcs[xSize][ySize];
	  System.out.println("Longest Common SubSequence Length is :"+counter);
	  System.out.println("----------------------------------------------");
      char[]lcsArray=new char[counter];
      int fill=0;
      int seen=0;	  
	  while(seen != counter)
	  {    
	      // System.out.print(marks[i][j]+"  ");
	       if(marks[i][j].equals("U"))
		   {
		      i=i-1;
		   }
		   else if(marks[i][j].equals("L"))
		   {
		      j=j-1;
		   }
		   else
		   {
		       lcsArray[fill]=xArray[i];
			   fill++;
		       i=i-1;
			   j=j-1;
			  seen++;
		   }
		   
	  }
	  System.out.print("Longest Common SubSequence is : ");
	  int lcsLength=lcsArray.length;
	  for(int k=0;k<lcsLength;k++)
	  {
	     System.out.print(lcsArray[lcsLength-k-1]);
	  }
	  System.out.println();
   
   }

}

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.