3
\$\begingroup\$

I am going one-by-one through problems in the "Cracking the Coding Interview". This question is about problem 1.5. One Away. Since I was never good in "algorithming", any suggestions are highly appreciated.

The very best thing you can do for me is suggest a better approach instead of the "straightforward" fragile code I wrote.

Oh, and since it's pretty much an interview question, performance is important too. The solution I got is O(n) -- bound by the length of the longest string so far (which can be easily fixed by early exit when mismatchCount exceeds 1).

Code

/**
 * Problem:
 *   There are three types of edits that can performed on strings:
 *   insert a character, remove a charachter, or replace a character.
 *   Given two strings, write a function to check if they are one edit (or zero edits) away.
 *
 * Example:
 *   pale, ple   -> true
 *   pales, pale -> true
 *   pale, bale  -> true
 *   pale, bake  -> false
 *
 * Solution:
 *   complexity: O(n)
 */

export function areOneAway(leftWord: string, rightWord: string): boolean {
  let leftIndex = 0;
  let rightIndex = 0;
  let mismatchCount = 0;

  while (leftIndex < leftWord.length && rightIndex < rightWord.length) {
    const leftChar = leftWord[leftIndex];
    const rightChar = rightWord[rightIndex];

    if (leftChar === rightChar) {
      leftIndex++;
      rightIndex++;
    } else {
      const nextLeftChar = leftWord[leftIndex + 1];
      const nextRightChar = rightWord[rightIndex + 1];

      const leftCharEqualsNextRight = leftChar === nextRightChar;
      const rightCharEqualsNextLeft = rightChar === nextLeftChar;
      const nextLeftEqualsNextRight = nextLeftChar === nextRightChar;

      if (nextLeftEqualsNextRight) {
        leftIndex++;
        rightIndex++;
      } else if (
        leftCharEqualsNextRight && rightCharEqualsNextLeft ||
        !leftCharEqualsNextRight && !rightCharEqualsNextLeft
      ) {
        return false;
      } else if (leftCharEqualsNextRight) {
        rightIndex++;
      } else if (rightCharEqualsNextLeft) {
        leftIndex++;
      } else {
        throw new Error('Invariant violated');
      }

      mismatchCount++;
    }
  }

  return ((leftWord.length - leftIndex) + (rightWord.length - rightIndex) + mismatchCount) <= 1;
}

Tests

import { expect } from 'chai';

import { areOneAway } from '../../src/cracking-the-coding-interview/1-5-one-away';

describe(`1-5: OneAway`, () => {
  [
    { string1: 'pale', string2: 'ple', expectedResult: true },
    { string1: 'pales', string2: 'pale', expectedResult: true },
    { string1: 'pale', string2: 'bale', expectedResult: true },
    { string1: 'pale', string2: 'bake', expectedResult: false },

    { string1: '', string2: '', expectedResult: true },
    { string1: '', string2: ' ', expectedResult: true },
    { string1: ' ', string2: '', expectedResult: true },
    { string1: '', string2: '  ', expectedResult: false },
    { string1: '  ', string2: '', expectedResult: false },
    { string1: '', string2: 'x  ', expectedResult: false },
    { string1: 'x  ', string2: '', expectedResult: false },
    { string1: 'a', string2: 'a', expectedResult: true },

    { string1: 'ab', string2: 'a', expectedResult: true },
    { string1: 'abc', string2: 'a', expectedResult: false },
    { string1: 'abc', string2: 'abc', expectedResult: true },
    { string1: 'a', string2: 'ab', expectedResult: true },
    { string1: 'a', string2: 'abc', expectedResult: false },

    { string1: 'xab', string2: 'xa', expectedResult: true },
    { string1: 'xabc', string2: 'xa', expectedResult: false },
    { string1: 'xabc', string2: 'xabc', expectedResult: true },
    { string1: 'xa', string2: 'xab', expectedResult: true },
    { string1: 'xa', string2: 'xabc', expectedResult: false },
  ].forEach(testCase => {
    const { string1, string2, expectedResult } = testCase;

    it(`Should return ${expectedResult} for '${string1}' and '${string2}'`, () => {
      expect(areOneAway(string1, string2)).to.equal(expectedResult);
    });
  });
});
\$\endgroup\$
2
\$\begingroup\$

Your code is almost exactly what I would write. The one slight improvement I can recommend is noticing that adding a character to the left string is the exact same thing as removing a character from the right string.

const areOneAway = (left, right) => {
  if (Math.abs(left.length - right.length) > 1) return false;
  let difference = 0;
  let indexLeft = 0;
  let indexRight = 0;
  while (difference < 2 && indexLeft < left.length && indexRight < right.length) {
    if (left[indexLeft] !== right[indexRight]) {
      difference++;
      // Character inserted in left string, or character removed in right string
      if (left[indexLeft + 1] === right[indexRight]) indexLeft++;
      // Character inserted in right string, or character removed in left string
      else if (left[indexLeft] === right[indexRight + 1]) indexRight++;
    }
    indexLeft++;
    indexRight++;
  }
  return difference < 2;
};


let passed = 0;
let failed = 0;

[
  { string1: 'pale', string2: 'ple', expectedResult: true },
  { string1: 'pales', string2: 'pale', expectedResult: true },
  { string1: 'pale', string2: 'bale', expectedResult: true },
  { string1: 'pale', string2: 'bake', expectedResult: false },

  { string1: '', string2: '', expectedResult: true },
  { string1: '', string2: ' ', expectedResult: true },
  { string1: ' ', string2: '', expectedResult: true },
  { string1: '', string2: '  ', expectedResult: false },
  { string1: '  ', string2: '', expectedResult: false },
  { string1: '', string2: 'x  ', expectedResult: false },
  { string1: 'x  ', string2: '', expectedResult: false },
  { string1: 'a', string2: 'a', expectedResult: true },

  { string1: 'ab', string2: 'a', expectedResult: true },
  { string1: 'abc', string2: 'a', expectedResult: false },
  { string1: 'abc', string2: 'abc', expectedResult: true },
  { string1: 'a', string2: 'ab', expectedResult: true },
  { string1: 'a', string2: 'abc', expectedResult: false },

  { string1: 'xab', string2: 'xa', expectedResult: true },
  { string1: 'xabc', string2: 'xa', expectedResult: false },
  { string1: 'xabc', string2: 'xabc', expectedResult: true },
  { string1: 'xa', string2: 'xab', expectedResult: true },
  { string1: 'xa', string2: 'xabc', expectedResult: false },
].forEach(testCase => {
  const { string1, string2, expectedResult } = testCase;

  if (expectedResult !== areOneAway(string1, string2)) {
    console.log(`Failed: areOneAway('${string1}', '${string2}') should be ${expectedResult}`);
    failed++;
  } else {
    passed++;
  }
});
console.log('Passed:', passed, 'Failed:', failed)

Of course, the next step for making this function more reusable would be to extract the difference calculation to a separate function.

const findDifference = (left, right) => {
  let difference = 0;
  let indexLeft = 0;
  let indexRight = 0;
  while (indexLeft < left.length && indexRight < right.length) {
    if (left[indexLeft] !== right[indexRight]) {
      difference++;
      if (left[indexLeft + 1] === right[indexRight]) indexLeft++;
      else if (left[indexLeft] === right[indexRight + 1]) indexRight++;
    }
    indexLeft++;
    indexRight++;
  }
  difference += left.length - indexLeft;
  difference += right.length - indexRight;
  return difference
}

let passed = 0;
let failed = 0;
[
  { string1: 'pale', string2: 'ple', expectedResult: 1 },
  { string1: 'pales', string2: 'pale', expectedResult: 1 },
  { string1: 'pale', string2: 'bale', expectedResult: 1 },
  { string1: 'pale', string2: 'bake', expectedResult: 2 },

  { string1: '', string2: '', expectedResult: 0 },
  { string1: '', string2: ' ', expectedResult: 1 },
  { string1: ' ', string2: '', expectedResult: 1 },
  { string1: '', string2: '  ', expectedResult: 2 },
  { string1: '  ', string2: '', expectedResult: 2 },
  { string1: '', string2: 'x  ', expectedResult: 3 },
  { string1: 'x  ', string2: '', expectedResult: 3 },
  { string1: 'a', string2: 'a', expectedResult: 0 },

  { string1: 'ab', string2: 'a', expectedResult: 1 },
  { string1: 'abc', string2: 'a', expectedResult: 2 },
  { string1: 'abc', string2: 'abc', expectedResult: 0 },
  { string1: 'a', string2: 'ab', expectedResult: 1 },
  { string1: 'a', string2: 'abc', expectedResult: 2 },

  { string1: 'xab', string2: 'xa', expectedResult: 1 },
  { string1: 'xabc', string2: 'xa', expectedResult: 2 },
  { string1: 'xabc', string2: 'xabc', expectedResult: 0 },
  { string1: 'xa', string2: 'xab', expectedResult: 1 },
  { string1: 'xa', string2: 'xabc', expectedResult: 2 },
].forEach(test => {
  const { string1, string2, expectedResult } = test
  const result = findDifference(string1, string2)
  if (result !== expectedResult) {
    console.log(`Failed: findDifference('${string1}', '${string2}') should be ${expectedResult}, got ${result}`);
    failed++;
  } else {
    passed++;
  }
});
console.log('Passed:', passed, 'Failed:', failed)

With this helper, areNAway could be implemented very easily and areOneAway could just be implemented as (left, right) => areNAway(left, right, 1)

const areNAway = (left, right, n) => {
  if (Math.abs(left.length - right.length) > n) return false;
  return findDifference(left, right) <= n;
}

P.S. You may be interested in the "Official" solution. It is available on GitHub.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Just got a baby born -- have no time to look through it with attention to all the details. Voting up though. May accept a bit later \$\endgroup\$ – Igor Soloydenko Nov 2 '17 at 3:08

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.