Похожие строки

средне

# решено

Даны две строки s и t. Строки считаются похожими, если они уже равны или могут стать равными после ровно одного изменения: вставки, удаления или замены одного символа. Нужно вернуть true, если строки похожи, иначе — false.

Пример 1:

Ввод: s = "iq", t = "ieq"
Вывод: true
Объяснение: можно добавить один символ и получить равные строки s = t

Пример 2:

Ввод: s = "qwe", t = "qwe"
Вывод: true

Пример 3:

Ввод: s = "abcd", t = "abcdef"
Вывод: false
Объяснение: Необходимо добавить два символа, чтобы строки стали равны.

Ограничения:

len(s) >= 0
len(t) >= 0

public class Solution
{
    public static bool IsSimilar(string s, string t)
    {
        if (Math.Abs(s.Length - t.Length) > 1)
        {
            return false;
        }

        int p1 = 0;
        int p2 = 0;
        int cntMistakes = 0;

        while (p1 < s.Length && p2 < t.Length)
        {
            if (s[p1] == t[p2])
            {
                p1++;
                p2++;
                continue;
            }

            cntMistakes++;
            if (cntMistakes > 1)
            {
                return false;
            }

            if (s.Length > t.Length)
            {
                p1++;
            }
            else if (s.Length < t.Length)
            {
                p2++;
            }
            else
            {
                p1++;
                p2++;
            }
        }

        return true;
    }
}

#include <string>
#include <cmath>

using namespace std;

bool isSimilar(string s, string t) {
    if (abs((int)s.size() - (int)t.size()) > 1) {
        return false;
    }

    int p1 = 0;
    int p2 = 0;
    int cntMistakes = 0;

    while (p1 < s.size() && p2 < t.size()) {
        if (s[p1] == t[p2]) {
            p1++;
            p2++;
            continue;
        }

        cntMistakes++;
        if (cntMistakes > 1) {
            return false;
        }

        if (s.size() > t.size()) {
            p1++;
        } else if (s.size() < t.size()) {
            p2++;
        } else {
            p1++;
            p2++;
        }
    }
    return true;
}

package main

func isSimilar(s, t string) bool {
    n, m := len(s), len(t)
    if n-m > 1 || m-n > 1 {
        return false
    }

    p1, p2 := 0, 0
    cntMistakes := 0

    for p1 < n && p2 < m {
        if s[p1] == t[p2] {
            p1++
            p2++
            continue
        }

        cntMistakes++
        if cntMistakes > 1 {
            return false
        }

        if n > m {
            p1++
        } else if m > n {
            p2++
        } else {
            p1++
            p2++
        }
    }
    return true
}

import java.util.*;

public class Solution {
    public boolean isSimilar(String s, String t) {
        if (Math.abs(s.length() - t.length()) > 1) {
            return false;
        }

        int p1 = 0;
        int p2 = 0;
        int cntMistakes = 0;

        while (p1 < s.length() && p2 < t.length()) {
            if (s.charAt(p1) == t.charAt(p2)) {
                p1++;
                p2++;
                continue;
            }

            cntMistakes++;
            if (cntMistakes > 1) {
                return false;
            }

            if (s.length() > t.length()) {
                p1++;
            } else if (s.length() < t.length()) {
                p2++;
            } else {
                p1++;
                p2++;
            }
        }
        return true;
    }
}

from typing import *

def is_similar(s: str, t: str) -> bool:
    if abs(len(s) - len(t)) > 1:
        return False

    p1 = 0
    p2 = 0
    cnt_mistakes = 0

    while p1 < len(s) and p2 < len(t):
        if s[p1] == t[p2]:
            p1 += 1
            p2 += 1
            continue

        cnt_mistakes += 1
        if cnt_mistakes > 1:
            return False

        if len(s) > len(t):
            p1 += 1
        elif len(s) < len(t):
            p2 += 1
        else:
            p1 += 1
            p2 += 1

    return True

/**
 * @param {string} s
 * @param {string} t
 * @returns {boolean}
 */
export function isSimilar(s, t) {
  if (Math.abs(s.length - t.length) > 1) {
    return false;
  }

  let p1 = 0;
  let p2 = 0;
  let cntMistakes = 0;

  while (p1 < s.length && p2 < t.length) {
    if (s[p1] === t[p2]) {
      p1 += 1;
      p2 += 1;
      continue;
    }

    cntMistakes += 1;
    if (cntMistakes > 1) {
      return false;
    }

    if (s.length > t.length) {
      p1 += 1;
    } else if (s.length < t.length) {
      p2 += 1;
    } else {
      p1 += 1;
      p2 += 1;
    }
  }
  return true;
}

Оценка сложности

Время: O(n), где n - длина самой длинной из строк s и t
Память: O(1)