Friday, August 24, 2012

Find the longest common sequence

Longest Common Sequence

Java Code:

/**
* Find the longest common sequence from two strings.
* @param seq1 String sequence 1.
* @param seq2 String sequence 1.
* @return  String of longest common sequence.
*/
public String getLCS(final String seq1, final String seq2)
{
// Check for empty.
if (!seq1.isEmpty() && !seq2.isEmpty())
{
// Separate 1st char & remaining part of 1st string.
String seq1B = seq1.substring(0,1);
String seq1E = seq1.substring(1);
// Separate 1st char & remaining part of 2nd string.
String seq2B = seq2.substring(0,1);
String seq2E = seq2.substring(1);

// Check for equality of start characters of both strings.
if (seq1B.equalsIgnoreCase(seq2B))
{
// If equal append character and check for rest part
return seq1B + getLCS(seq1E, seq2E);
}
else
{
// Check for both strings and return the greater results.
String ret1 = getLCS(seq1, seq2E);
String ret2 = getLCS(seq1E, seq2);
if (ret1.length() > ret2.length())
{
return ret1;
}
else
{
return ret2;
}
}
}
else
{
return "";
}
}

Example:
getLCS("HUMAN", "CHIMPANZEE") ==> HMAN

How to check if the given string is palindrome?

Algorithm:
Approach1 : Start comparing characters from start and end of the string and continue until len(string)/2 .
Approach2: Start from front and back and compare the characters if not equal exit and return false else return true

Java Code:

public boolean isPalindrom(String str)
{
int length = str.length();
for(int i=0; i< length/2 ;i++)
{
if(str.charAt(i) != str.charAt(length - 1 - i))
{
System.out.println(str + " is not a palindrom." );
return false;
}
}
System.out.println(str + " is a palindrom." );
return true;
}

Example:
isPalindrom("abqba") ==> true
isPalindrom("abba") ==> true
isPalindrom("abstba")  ==> false
isPalindrom("absa")  ==> false

Ruby Code:

def palindrom(str)
  start = 0
  last = str.size - 1
  array_str = str.chars
  is_palindrom = true
  while (start < last)
    if array_str[start] != array_str[last]
      is_palindrom = false
      break
    end
    start+=1
    last-=1
  end
  is_palindrom
end

p palindrom("radar")
p palindrom("r")
p palindrom("123456")
p palindrom("rr")
p palindrom("radbar")

p palindrom("1radar1")