DEV Community

wkw
wkw

Posted on

2 1

BinarySearch - One Edit Distance

https://binarysearch.com/problems/One-Edit-Distance

Problem

Given two strings s0 and s1 determine whether they are one or zero edit distance away. An edit can be described as deleting a character, adding a character, or replacing a character with another character.

Constraints

n ≤ 100,000 where n is the length of s0.
m ≤ 100,000 where m is the length of s1.

Solution

Find the first index i that s0[i] is not equal to s1[i]

Based on the length of s0 and s1, compare the rest of the sub string are same or not.

bool solve(string s0, string s1) {
    int m = s0.size(), n = s1.size();
    for (int i = 0; i < min(m, n); i++) {
        if (s0[i] != s1[i]) {
            if (m == n)
                return s0.substr(i + 1) == s1.substr(i + 1);
            else if (m < n)
                return s0.substr(i) == s1.substr(i + 1);
            else
                return s0.substr(i + 1) == s1.substr(i);
        }
    }
    return abs(m - n) <= 1;
}
Enter fullscreen mode Exit fullscreen mode

Hostinger image

Get n8n VPS hosting 3x cheaper than a cloud solution

Get fast, easy, secure n8n VPS hosting from $4.99/mo at Hostinger. Automate any workflow using a pre-installed n8n application and no-code customization.

Start now

Top comments (0)

Qodo Takeover

Introducing Qodo Gen 1.0: Transform Your Workflow with Agentic AI

Rather than just generating snippets, our agents understand your entire project context, can make decisions, use tools, and carry out tasks autonomously.

Read full post

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay