lintcode 640. 一次编辑距离

约定不等于承诺〃 2023-07-17 15:41 17阅读 0赞

给定两个字符串 S 和 T, 判断T是否可以通过对S做刚好一次编辑得到。  
每次编辑可以选择以下任意一个操作：

在S的任意位置插入一个字符  
删除S中的任意一个字符  
将S中的任意字符替换成其他字符

样例
    例1:
    
    输入: s = "aDb", t = "adb" 
    输出: true
    例2:
    
    输入: s = "ab", t = "ab" 
    输出: false
    解释:
    s=t ,所以他们不相差一次编辑的距离

class Solution {
        
    public:
        /**
         * @param s: a string
         * @param t: a string
         * @return: true if they are both one edit distance apart or false
         */
        bool isOneEditDistance(string &s, string &t) {
        
            // write your code here
            int len1=s.size();
            int len2=t.size();
            if(abs(len1-len2)>=2) return false;
            else if(len1==len2)
            {
        
                int flag=0;
                for (int i = 0; i < len1; i++) {
        
                    if(s[i]!=t[i]) flag++;
                }
                if(flag!=1) return false;
                return true;
            }
            else if(len1>len2)
            {
        
                int ps=0;
                int pt=0;
                while(ps<len1&&pt<len2)
                {
        
                    if(s[ps]==t[pt])
                    {
        
                        ps++;
                        pt++;
                    }
                    else
                    {
        
                        ps++;
                    }
                }
                if(pt==len2) return true;
                return false;
            }
            else
            {
        
                int ps=0;
                int pt=0;
                while(ps<len1&&pt<len2)
                {
        
                    if(s[ps]==t[pt]) 
                    {
        
                        ps++;
                        pt++;
                    }
                    else
                        pt++;
                }
                if(ps==len1) return true;
                return false;
            }
        }
    };