Cracking the Coding Interview: "Problem 1.5. One Away"

Question

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);
    });
  });
});

Answer 1

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.

Answer 2

There are multiple ways to convert from one string to another, but the function doesn't always find the one with the least edits.

Try for example, aaaba and aaba. One a has been added to the beginning, but the function returns false.

In general, trying to count the number of edits would require quadratic time as it's the Levenshtein distance but it can be solved for a distance of 1 by focusing on what happens when the strings differ in length by either 0 or 1 characters. For 0, only one character can be replaced, and for 1, only one character can be inserted.

Answer 3

I was never good in "algorithming"

You start skipping a common prefix - when it is each string, you're done.
Fine if there is no "sub-linear" way to determine the length of a string.
(If there is, length differs by more than one is a decent pre-check.)

But when hitting a difference, you get into details.

Instead, look for a common suffix:
If, in the longest string, first and last difference are at the same index, the edit distance is one.
(For an entirely different approach as easy to implement, follow the hyperlink Gerrit0 provided. (Quite close to yours adding "early out", I think.) I find it more difficult to describe and think up - mileages differ.)

---

I like the problem summary in the procedure comment (stylised the way of JSDoc comments - there are bound to be guidelines for documenting procedures), and that you include a test - fgb's answer suggests room for improvement in the test cases.

The name areOneAway() picks up the problem title - fine, but it returns true even if the strings a "zero away", identical.

Your access to "next" characters may be to a character "one beyond" the shortest string. No idea whether that's fine with TypeScript - I'd appreciate a code comment, anyway.

You present code to throw an Error('Invariant violated'): I'd appreciate the invariant explicitly appearing in the code, and more helpfully worded in the Error string, if possible.

I find the indentation of the multi-line condition in the first else-if in the if-else-if chain less than helpful. I prefer parenthesised contents indented at least as far as (the line containing) the opening bracket (even if that spelled begin).

Answer 4

Your approach will take you to the solution but as you already noticed it is quite fragile. If I will ask you to make amends to your code or gave you an extended problem, it would be hard to make those changes. There are too many conditions that are hard to understand and makes code a bit of a hassle.

Instead, if you think of all the requirements as an interactive approach and try to derive a crips solution then it would be helpful. So, as you asked for an alternative approach I could think of something like the one below.

I followed an iterative approach to solve this problem.

• if both words are of the same length then count mismatching characters, it should not be more than 1.
• if the difference in the length of both words is greater than 1 then return false
• count mismatch characters, it should not be more than 1.

public boolean checkIfBothWordsAreOneOrZeroEditAway(String firstWord, String secondWord) {
        var i = 0;
        var j = 0;
        var misMatch = 0;

        if (firstWord.length() == secondWord.length()) {
            while (i < firstWord.length()) {
                if (firstWord.charAt(i) != secondWord.charAt(i))
                    misMatch++;
                i++;
            }

            return misMatch <= 1;
        }

        var biggerWord = firstWord.length() > secondWord.length() ? firstWord : secondWord;
        var smallerWord = firstWord.length() == biggerWord.length() ? secondWord : firstWord;
        if (biggerWord.length() - smallerWord.length() > 1) return false;

        i = 0;
        misMatch = 0;
        while (i < smallerWord.length()) {
            if (smallerWord.charAt(i) != biggerWord.charAt(j)) {
                misMatch++;
                if (misMatch > 1) return false;
            } else {
                i++;
            }
            j++;
        }

        return true;
    }

You can take this code and try to optimize it further. I hope it's helpful.