One Edit Distance

Description

null

Solution(javascript)

// /** 1: Edit Distance O(n^2) Time Limited Exceed
//  * @param {string} s
//  * @param {string} t
//  * @return {boolean}
//  */
// const isOneEditDistance = function (s, t) {
//   const memo = {}
//   const aux = (index1, index2) => {
//     const key = `${index1}-${index2}`
//     if (memo[key] !== undefined) {
//       return memo[key]
//     }
//     if (index1 >= s.length) {
//       return t.length - index2
//     }
//     if (index2 >= t.length) {
//       return s.length - index1
//     }
//     if (s[index1] === t[index2]) {
//       return aux(index1 + 1, index2 + 1)
//     }
//     memo[key] = 1 + Math.min(
//       aux(index1 + 1, index2 + 1), // replace
//       aux(index1 + 1, index2),
//       aux(index1, index2 + 1),
//     )
//     return memo[key]
//   }
//   return aux(0, 0) === 1
// }


/** 2:
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
const isOneEditDistance = function (s, t) {
  if (Math.abs(s.length - t.length) > 1) {
    return false
  }
  if (s.length === t.length) { // replace
    let diffSize = 0
    for (let i = 0; i < s.length; i++) {
      if (s[i] !== t[i]) {
        diffSize += 1
      }
      if (diffSize > 1) {
        return false
      }
    }
    return diffSize === 1
  }
  // delete one character from the longer string
  const longer = s.length > t.length ? s : t
  const shorter = s.length > t.length ? t : s
  let skipSize = 0
  let j = 0
  for (let i = 0; i < longer.length; i++) {
    if (longer[i] !== shorter[j]) {
      skipSize += 1
    } else {
      j++
    }
    if (skipSize > 1) {
      return false
    }
  }
  return skipSize === 1
}