Does recursion in code still make my code linear to string length


This Content is from Stack Overflow. Question asked by Danny Shen

Let’s say I have two string s and t and I want to know if I can get from s to t via deleting, inserting or replacing a character in s. I have the following algorithm:

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        return onedistance(s, t, 0, 0, 0);
    private boolean onedistance(String s, String t, int si, int ti, int count) {
        if(count > 1) return false;
        while(si < s.length() || ti < t.length()) {
            if(si == s.length()) return onedistance(s, t, si, ti + 1, count + 1);
            if(ti == t.length()) return onedistance(s, t, si + 1, ti, count + 1);
            if(s.charAt(si) == t.charAt(ti)) {
            } else {
                return onedistance(s, t, si + 1, ti, count + 1) || 
                    onedistance(s, t, si, ti + 1, count + 1) || 
                    onedistance(s, t, si + 1, ti + 1, count + 1);
        return count == 1;

Basically the idea is to keep track of current pointer si and ti for character we are comparing now for s and t, if they are the same move both pointer forward, else move either si or ti or both to represent adding, deleting or replacing a char in s, we can only do it once, so if count > 1 we return false, at the end we check if count is equal to one to know if edit distance between s and t is 1.

I am wondering now if my code is O(m + n) where m and n is length of s and t, because even we have the recursive part, we only do it once and return immediately if count > 1;


This question is not yet answered, be the first one who answer using the comment. Later the confirmed answer will be published as the solution.

This Question and Answer are collected from stackoverflow and tested by JTuto community, is licensed under the terms of CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.

people found this article helpful. What about you?