Function isAbbreviation

Dynamic-Programming/Abbreviation.js:15–47

(source, target)

 * @see https://www.hackerrank.com/challenges/abbr/problem - Related problem on HackerRank.
 */
export const isAbbreviation = (source, target) => {
  const sourceLength = source.length
  const targetLength = target.length

  // Initialize a table to keep track of possible abbreviations
  let canAbbreviate = Array.from({ length: sourceLength + 1 }, () =>
    Array(targetLength + 1).fill(false)
  )
  // Empty strings are trivially abbreviatable
  canAbbreviate[0][0] = true

  for (let sourceIndex = 0; sourceIndex < sourceLength; sourceIndex++) {
    for (let targetIndex = 0; targetIndex <= targetLength; targetIndex++) {
      if (canAbbreviate[sourceIndex][targetIndex]) {
        // If characters at the current position are equal, move to the next position in both strings.
        if (
          targetIndex < targetLength &&
          source[sourceIndex].toUpperCase() === target[targetIndex]
        ) {
          canAbbreviate[sourceIndex + 1][targetIndex + 1] = true
        }
        // If the current character in `source` is lowercase, explore two possibilities:
        // a) Capitalize it (which is akin to "using" it in `source` to match `target`), or
        // b) Skip it (effectively deleting it from `source`).
        if (source[sourceIndex] === source[sourceIndex].toLowerCase()) {
          canAbbreviate[sourceIndex + 1][targetIndex] = true
        }
      }
    }
  }

  return canAbbreviate[sourceLength][targetLength]
}