Longest Com­mon Sub­se­quence Naive- Algo 3

Problem statement task: Given two string sequences, write an algo­rithm to find the length of longest sub­se­quence present in both of them.

These kind of dynamic pro­gram­ming ques­tions are very famous in the inter­views like Ama­zon, Microsoft, Ora­cle and many more.

What is Longest Com­mon Sub­se­quence: A longest sub­se­quence is a sequence that appears in the same rel­a­tive order, but not nec­es­sar­ily contiguous(not sub­string) in both the string.

Exam­ple:

String A = "acbaed";

String B = "abcadf";

Longest Common Subsequence(LCS):     acad, Length: 4

Java Implementation using multiple loop

public class LCSNaive {

      public static void main(String[] args) {

            String str1 = "ACBDEA";

            String str2 = "ABCDA";

            String result = lcs(str1, str2);

            System.out.println(result);

      }

      static String lcs(String str1, String str2) {

            int len1 = str1.length();

            int len2 = str2.length();

            int j = 0, ji = 0;

            String result = "";

            for (int i = 0; i < len1; i++) {

                  for (; j < len2; j++) {

                        if (str1.charAt(i) == str2.charAt(j)) {

                              result += str1.charAt(i);

                              ji = j;

                              break;

                        }

                  }

                  if (j == len2)

                        j = ji + 1;

            }

            return result;

      }

}

Output:

ACDA