// Determine if a string is one edit away from another.

#define CATCH_CONFIG_MAIN
#include <catch.hpp>

#include <cassert>
#include <experimental/string_view>
#include <range/v3/all.hpp>
#include <string>
#include <unordered_map>

using namespace ranges;
using string_view = std::experimental::string_view;

bool is_insert(string_view lhs, string_view rhs) {
  assert(lhs.length() < rhs.length());
  auto lh = lhs.cbegin();
  auto rh = rhs.cbegin();

  // Skip the matching characters.
  for (; *lh == *rh && lh != lhs.cend();) {
    lh++;
    rh++;
  }
  // Skip the inserted character.
  rh++;

  // Rest should match.
  return string_view(lh, lhs.cend() - lh) == string_view(rh, rhs.cend() - rh);
}

bool one_edit(string_view lhs, string_view rhs) {
  if (lhs.length() == rhs.length()) {
    // Possible change.
    int diffs = 0;
    for (const auto& pair : view::zip(lhs, rhs)) {
      if (pair.first != pair.second) {
        diffs++;
      }
    }
    return diffs <= 1;
  } else if (lhs.length() < rhs.length()) {
    return is_insert(lhs, rhs);
  } else if (lhs.length() > rhs.length()) {
    return is_insert(rhs, lhs);
  }

  return false;
}

TEST_CASE("cc15", "edits") {
  CHECK(is_insert("", "a") == true);
  CHECK(is_insert("a", "ab") == true);
  CHECK(is_insert("abc", "abdc") == true);
  CHECK(is_insert("bc", "abc") == true);

  CHECK(one_edit("pale", "ple") == true);
  CHECK(one_edit("pales", "pale") == true);
  CHECK(one_edit("pale", "pales") == true);
  CHECK(one_edit("pale", "bale") == true);
  CHECK(one_edit("pale", "bake") == false);
}