I've seen this today on a mock interview and wanted to give it a try. I'd love to hear some feedback from you guys. This is my second attempt at the problem, initially I had a mess of if/else towers and nested loops.
/*
* Write a function that takes two strings s1 and s2 and returns the
* longest common subsequences of s1 and s2.
*
* Examples:
* s1: ABAZDC s2: BACBAD result: ABAD
* s1: AGGTAB s2: GXTXAYB result: GTAB
* s1: aaaa s2: aa result: aa
* s1: aaaa s2: '' result: ''
*/
public class LongestSubsequence {
public static void main(String[] args) {
LongestSubsequence ls = new LongestSubsequence();
assertEquals("ABAD", ls.solve("ABAZDC", "BACBAD"));
assertEquals("GTAB", ls.solve("AGGTAB", "GXTXAYB"));
assertEquals("aa", ls.solve("aaaa", "aa"));
assertEquals("", ls.solve("aaaa", ""));
assertEquals("ABAD", ls.solve("BACBAD", "ABAZDC"));
assertEquals("aaaa", ls.solve("bcaaaa", "aaaabc"));
assertEquals("aaaa", ls.solve("bcaaaade", "deaaaabc"));
}
private String solve(String s1, String s2) {
if (s1.length() == 0 || s2.length() == 0) {
return "";
}
String subSeq1 = getLongestSubsequence(s1, s2);
String subSeq2 = getLongestSubsequence(s2, s1);
return (subSeq1.length() >= subSeq2.length() ? subSeq1 : subSeq2);
}
private String getLongestSubsequence(String first, String second) {
String retValue = "";
int currentIndex = 0;
for (int remaining = first.length(); retValue.length() < remaining; remaining--) {
StringBuilder firstWorker = new StringBuilder(first.substring(currentIndex));
StringBuilder secondWorker = new StringBuilder(second);
StringBuilder possibleSequence = new StringBuilder();
while (firstWorker.length() > 0 && secondWorker.length() > 0) {
String ch = firstWorker.substring(0, 1);
int firstIndex = secondWorker.indexOf(ch);
if (firstIndex != -1) {
possibleSequence.append(ch);
secondWorker.delete(0, firstIndex + 1);
}
firstWorker.delete(0, 1);
}
if (possibleSequence.length() > retValue.length()) {
retValue = possibleSequence.toString();
}
currentIndex++;
}
return retValue;
}
}
