Tuesday, January 3, 2017

Leetcode/各大家--161. One Edit Distance(substring)

161. One Edit Distance(substring)
  • Difficulty: Medium
https://leetcode.com/problems/one-edit-distance/


Given two strings S and T, determine if they are both one edit distance apart.

Company:



思路:一共有3种情况满足1edit distance
         case1:len1 = len2, "abc" vs "adc"//replace one char from str1 
                    1: check if diff > 1
         case2: len1 - len2 = 1,"abc" vs "ac" //delete one char from str1
         case3: len2 - len1 = 1, "ab" vs "abc";//delete one char from str2
                   2.3 find the different char, compare the rest of substring

关键字: substring, str.equals(str2);


public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int count =0;
        int len1 = s.length(), len2 = t.length();
        if(len1 == len2){
            for(int i = 0; i < s.length(); i++){
                if(s.charAt(i) != t.charAt(i)) count++;
                if(count > 1) return false;
            }
            return !s.equals(t);
        }else if(len1 - len2 == 1||len1 - len2 == -1){
            int i = 0, j = 0;
            while(i < len1 && j < len2){
                if(s.charAt(i) != t.charAt(j)){
                    String tmp1, tmp2;
                    if(len1 < len2){ 
                        tmp1 = s.substring(i, len1);
                        tmp2 = t.substring(j + 1, len2);
                    }else{
                        tmp1 = s.substring(i + 1, len1);
                        tmp2 = t.substring(j, len2);
                    }
                    return tmp1.equals(tmp2);
                }
                i++;
                j++;
            }
            return true;//"a", ""
        }
        return false;
        
    }
}

No comments:

Post a Comment