# 161 One Edit Distance

給兩個String, S和T判斷兩者是否只要做一個編輯就可以變成對方。

這邊題意有點不清楚，一開始我先列出可能的情況和不清楚的地方

//add
a
ab

//replace
ax
ab

//insert(不確定算不算)
ab
acb

//字母的大小寫算相同還是不同？

先寫了可以add和replace的版本之後，實際跑case發現insert也算，然後大小寫視為不同。

• Idea: 一找到不一樣的字母，就把長的跳過一個，check後面的substring是否相等

• Code: 這個解法其實不太快，後來觀察其他人的做法，發現其實最後一個for可以省略，用substring和equals就好

  public class Solution {
      public boolean isOneEditDistance(String s, String t) {
          //base case: 長度相差超過1，就不可能了    
          if(Math.abs(s.length() - t.length()) > 1)
              return false;
  
          //一一比對字母，一有不同就截斷
          int i=0, j=0;
          boolean dif = false;
          for(; i<s.length() && j< t.length(); i++, j++){
              if(s.charAt(i)!=t.charAt(j)){
                  dif = true;
                  break;
              }
          }
  
          //把長的那個跳過一格，繼續檢查後面的，後面若再有不同就是false，後面若都相同就true
          if(i == s.length() && j == t.length())//兩個都走到最後一個字母時，確認最後一個字母一不一樣
              return dif;
  
          if(s.length() > t.length()) i++;
          else if(t.length() > s.length()) j++;
          else{i++; j++;}
  
          for(; i<s.length() && j< t.length(); i++, j++)
              if(s.charAt(i)!=t.charAt(j))    return false;
  
          return true;
      }
  }
  

• Code(optimize): 把第二個for拿掉看起來比較簡潔。

  public class Solution {
      public boolean isOneEditDistance(String s, String t) {
          //base case: 長度相差超過1，就不可能了    
          if(Math.abs(s.length() - t.length()) > 1)
              return false;
  
          for (int i = 0; i < Math.min(s.length(), t.length()); i++) { 
              if (s.charAt(i) != t.charAt(i)) {
                  if (s.length() == t.length()) 
                      // s has the same length as t, so the only possibility is replacing one char in s and t
                      return s.substring(i + 1).equals(t.substring(i + 1));
                  else if (s.length() < t.length()) // t is longer than s, so the only possibility is deleting one char from t
                      return s.substring(i).equals(t.substring(i + 1));                
                  else // s is longer than t, so the only possibility is deleting one char from s
                      return t.substring(i).equals(s.substring(i + 1));
              }
          }       
          //All previous chars are the same, the only possibility is deleting the end char in the longer one of s and t 
          return Math.abs(s.length() - t.length()) == 1;  
      }
  }