1
\$\begingroup\$

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'));
\$\endgroup\$
  • \$\begingroup\$ Why not loop from the end until they do not match, and then return from there to to end of the string? \$\endgroup\$ – spyr03 Nov 18 '15 at 14:47
  • \$\begingroup\$ The problem asked for a recursive solution, but ya that would work. \$\endgroup\$ – Daniel Jacobson Nov 18 '15 at 14:54
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I really like how you use the negative in your slices ;) \$\endgroup\$ – Daniel Jacobson Dec 11 '15 at 2:07
0
\$\begingroup\$

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 '';
    }
};
\$\endgroup\$
  • \$\begingroup\$ LCSuffRec('hello', 'hello') errors :) \$\endgroup\$ – RobH Nov 18 '15 at 15:46
0
\$\begingroup\$

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 :)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.