#!/usr/bin/env python3
# Copyright 2021 The ChromiumOS Authors
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.
"""General-purpose utility functions that don't belong elsewhere."""


def levenshtein_distance(aa: str, bb: str) -> int:
  """Compute the Levenshtein distance between two strings.

    This is the minimum number of single-character edits required to change aa
    into bb and serves usefully as a distance metric between strings.

    Args:
      aa: first string
      bb: second string

    Returns:
      Edit distance between aa and bb.
    """

  # pylint: disable=invalid-name

  # We're effectively building a matrix of distances between two prefixes
  # of the strings:
  #
  #     0 1 2 3
  #    │ │c│a│t│
  #   ─┼─┼─┼─┼─┼
  # 0 s│1│1│2│3│
  #   ─┼─┼─┼─┼─┼
  # 1 a│2│2│1│2│
  #   ─┼─┼─┼─┼─┼
  # 2 d│3│3│2│2│
  #
  # But, if we don't want the _actual_ edit sequence, we can just keep the
  # first two rows.

  # if bb is empty, edit distance is just deleting aa.
  if not bb:
    return len(aa)

  # similarly, if aa is empty, edit distance is just inserting bb.
  if not aa:
    return len(bb)

  prev_dist = list(range(len(bb) + 1))
  curr_dist = [0] * (len(bb) + 1)

  for ii, chara in enumerate(aa):
    # we can always remove ii+1 characters to match the empty string.
    curr_dist[0] = ii + 1

    # compute cost of each of three operations from previous
    # distances and choose the cheapest one.
    for jj, charb in enumerate(bb):
      cost_delete = prev_dist[jj + 1] + 1
      cost_insert = curr_dist[jj] + 1
      cost_change = prev_dist[jj]
      if chara != charb:
        cost_change += 1

      curr_dist[jj + 1] = min(cost_delete, cost_insert, cost_change)

    # swap
    curr_dist, prev_dist = prev_dist, curr_dist

  return prev_dist[-1]