leetcode-程序员面试金典-字符串比较

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入:
first = "pale"
second = "ple"
输出: True
示例 2:
输入:
first = "pales"
second = "pal"
输出: False
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/one-away-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

看完之后，立刻根据三种情况开始处理.....

insert和delete都是使用的之前回文序列的较为繁琐的去重方法搞定的，bug来源就这里了。

也怪我没怎么好好理解题的意思，英文版的更好明白一点，只能是“one/zero edit”才能返回true，其他情况统统是false。
这样的话对字符串的匹配程度应该要求很高，insert和delete的处理过于粗糙了。

class Solution {
    //采用回文的去重思路判断insert和delete
    Set<Character> set_in = new HashSet<>();
    Set<Character> set_delete = new HashSet<>();

    public boolean oneEditAway(String first, String second) {

        //判断replace情况时候使用两个索引
        //分别指向index1和index2
        int index1;
        int index2;

        int count=0;
        index1=index2=0;

    String newstring= new String();
        //连接两个字符串
        newstring = first;
        //字符串中应该至多有一个重复字符
        newstring = newstring.concat(second);

        //转换成字符数组
        char[] chars_in = newstring.toCharArray();
        char[] chars_del = newstring.toCharArray();

        /**
         * 如果是需要插入一次*/
        if(first.length()==second.length()-1){

            for(Character character: chars_in){
                if(!set_in.contains(character))
                    set_in.add(character);
                else set_in.remove(character);
            }
        }
        /**
         * 如果是需要删除一次
         * */
        else if(first.length()==second.length()+1){

            for(Character character: chars_del){
                if(!set_delete.contains(character))
                    set_delete.add(character);
                else set_delete.remove(character);
            }
        }
        /**
         * 如果是长度相等**/
        else  if(first.length()==second.length()){

            //先判断是否是完全相等
            if(first.equals(second))
                return true;
                //判断replace数量
            else
                while(index1<first.length()||index2<second.length())
                {
                    if(first.charAt(index1)!=second.charAt(index2))
                    {
                        count++;
                    }
                    index1++;
                    index2++;
                }
        }

        if(set_in.size()==1) return true;
        if(set_delete.size()==1) return true;
        //如果count==1 return true ，else false
        if(count==1) return true;

        return false;
    }
}

然后测试不通过，看到用例我才傻眼了

first: teacher
second: detacher
这。。set去重完全搞不定啊
彻底傻眼.jpg
os：insert和replace你给我混用？？？

这样的情况下字符串完美匹配就非常重要了，因为从测试用例知道不能仅仅要求字符串的字符元素匹配，还得要求字符顺序也匹配。

最后采用双索引方法通过，用时2ms

class Solution {


    public boolean oneEditAway(String first, String second) {

        int i,j,k;
        i=0;
        k=first.length()-1;
        j=second.length()-1;

        //必定为错的情况
        if(Math.abs(k-j)>1) return false;

        char[] charsf = first.toCharArray();
        char[] charss = second.toCharArray();

        //双指针，从字符串的两端开始匹配
        //两个字符串最少需要三个index
      
        //指针移动的true condition：首尾指针相遇
        //指针移动时候必须保证两个字符串指针的同步移动
        while(i<first.length() && i<second.length() && charsf[i] == charss[i])
        {
            i++;
        }
        //踩坑记录：索引千万不要写反了！！
        while(k>=0 && j>=0 && charsf[k]==charss[j]){
            k--; j--;
        }
        if(k-i<1&& j-i<1)
        return true;
        else return false;

    }
}