161 One Edit Distance

来源：Leetcode, Facebook Onsite

原帖：https://leetcode.com/problems/one-edit-distance/

问题：
Given two strings S and T, determine if they are both one edit distance apart.
思路：
fb的高频题了。onsite的时候大脑短路竟然写出了一个bug。首先考虑corner case, 长度相差>=2, 长度相等(s == t), 长度相差1和长度相同但是(s!=t)。这道题有两种思路。I) 第一种思路比较简单，代码也不容易写错。就是同时遍历两个字符串到到第一个不同的地方，然后根据长度判断两个remaining子串是否相等。II) 每一个字符相互比较。当找到第一个不匹配的地方，根据S,T的长度选择i++,j++,还是i++。另外需要最后处理一个corner case. 

代码：1]

 class Solution {   
 public:   
     bool isOneEditDistance(string s, string t) {   
         int M = s.size(), N = t.size();   
         if (s == t) return false;   
         if (abs(M - N) > 1) return false;   
         if (N > M) return isOneEditDistance(t,s);   
         for (int i = 0; i < min(M,N); ++i) {   
             if (s[i] != t[i]) {   
                 return M == N ? s.substr(i+1) == t.substr(i+1) : s.substr(i+1) == t.substr(i);   
             }   
         }   
         return true;   
     }   
 };   

代码：2]

 class Solution {   
 public:   
     bool isOneEditDistance(string s, string t) {   
         int M = s.size(), N = t.size();    
         if (abs(M - N) > 1) return false;   
         if (M < N) return isOneEditDistance(t, s);   
         int count = 0, i = 0, j = 0;   
         while (i < M && j < N) {   
             if (s[i] != t[j]) {   
                 count++;   
                 if (count >= 2) return false;   
                 if (M == N) {   
                     i++; j++;   
                 } else {   
                     i++;   
                 }   
             } else {   
                 i++; j++;   
             }   
         }       
         if (i == M-1) count++;   
         return count == 1;   
     }   
 };