Finding the longest common suffix recursively

Question

I'm getting the correct results, but my method isn't the prettiest. Is there any way to do this with less code?

var longestSuffix = function(A, B) {
 return rec(A, B, 0);
 function rec(A, B, count) {
 if (!A.length || !B.length) return '';
 if (A[A.length - count - 1] === B[B.length - count - 1]) {
 console.log(A[A.length-count-1]);
 return rec(A, B, ++count) + A[A.length - count - 2];
 }
 return rec('','');
 }
};
console.log(longestSuffix('cababa', 'cabjklaba'));

• spyr03: Why not loop from the end until they do not match, and then return from there to to end of the string?
• Daniel Jacobson: The problem asked for a recursive solution, but ya that would work.

Answer 1

Recursive Solution Improvement

First, here's a rewrite of the answer you submitted yourself, which fixes a small bug and removes the inner function, which isn't needed. Instead, we make the final two parameters optional:

function longestSuffix(X,Y,m,n) {
 var m = m === undefined ? X.length : m, 
 n = n === undefined ? Y.length : n, 
 keepGoing = X[m-1] && Y[n-1] && X[m-1] === Y[n-1];
 return keepGoing ? longestSuffix(X, Y, m-1, n-1) + X[m-1] : '';
};

Here's a different approach, slightly longer because I spelled everything out with variable names, but perhaps simpler in concept:

function longestSuffix (A, B, answer) {
 var answer = answer || '',
 aLast = A.slice(-1),
 bLast = B.slice(-1),
 A = A.slice(0,-1),
 B = B.slice(0,-1),
 done = !aLast || !bLast || aLast != bLast;
 return done ? answer : longestSuffix(A, B, aLast + answer);
};

You can make it shorter by, eg, removing aMinusLast and bMinusLast and replacing them inline with their definitions, but I like this expanded version because everything is clearly named, and the entire logic of the function can be seen at a glance in a single line.

Loop solution

A loop may be more appropriate here. Here's a very brief implementation which takes advantage of slice, which exists on strings as well as arrays.

The only ugly part of this is that we have to treat the case when both A fully matches B as a special case in the return statement. Otherwise note that the final slice(1) just adjusts back for the final decrement.

function longestSuffix (A, B) {
 var i = -1;
 while (A.slice(i) == B.slice(i) && i >= -A.length) i--;
 return i < -A.length ? A : A.slice(i).slice(1)
};

This could be expanded for further clarity, but I figured I'd leave this one in compressed form, because it's so short.

• Daniel Jacobson: I really like how you use the negative in your slices ;)

Answer 2

Here it is a little cleaner in the sense that it is about 2 line less code and it doesn't do the return rec('','') to stop the recursion (which i thought was kind of ugly.

var LCSuffRec = function(X,Y) {
 return rec(X,Y, X.length, Y.length);
 function rec(X, Y, m, n) {
 if (X[m-1] === Y[n-1]) return rec(X, Y, m-1, n-1) + X[m-1];
 else return '';
 }
};

• RobH: LCSuffRec('hello', 'hello') errors :)

Answer 3

What about this:

var longestCommonSuffix = function (left, right) {
 if (!left || !right) {
 return '';
 }
 var leftLength = left.length,
 rightLength = right.length;
 var longestCommonSuffixInternal = function(step) {
 if (step > leftLength || step > rightLength || left[leftLength - step] !== right[rightLength - step]) {
 return '';
 }
 return longestCommonSuffixInternal(step + 1) + left[leftLength - step];
 }
 return longestCommonSuffixInternal(1); 
}

It passes these cases which yours doesn't:

longestCommonSuffix('hello', 'hello') // hello
longestCommonSuffix('', '') // ''
longestCommonSuffix('', null) // ''

I think it would be sufficient to only check that step has gone over the length of one of the two strings and not both but I left both checks in for completeness. It's not as elegant, but make something work first and then make it pretty :)