​LeetCode刷題實戰161:相隔為1的編輯距離

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 相隔為 1 的編輯距離  ，我們先來看題面：https://leetcode-cn.com/problems/one-edit-distance/

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

題意給定兩個字符串 s 和 t，判斷他們的編輯距離是否為 1。

示例 1：

輸入: s = "ab", t = "acb"
輸出: true
解釋: 可以將 'c' 插入字符串 s 來得到 t。

示例 2:

輸入: s = "cab", t = "ad"
輸出: false
解釋: 無法通過 1 步操作使 s 變為 t。

示例 3:

輸入: s = "1203", t = "1213"
輸出: true
解釋: 可以將字符串 s 中的 '0' 替換為 '1' 來得到 t。

解題https://blog.csdn.net/hebtu666/article/details/104107779但是稍微有一點優化，其實如果s能刪除一個字符變成t，那麼t一定也可以插入一個字符得到s。所以刪除插入沒必要都寫，我們把短的字符串放在左邊（s)，就不用寫刪除了。

class Solution {
  public boolean isOneEditDistance(String s, String t) {
    int ns = s.length();
    int nt = t.length();
    //交換
    if (ns > nt)
      return isOneEditDistance(t, s);
    //長度差超過1
    if (nt - ns > 1)return false;
    //找到不同的字符
    for (int i = 0; i < ns; i++)
      if (s.charAt(i) != t.charAt(i))
        //如長度不同，那麼兩字符串後面應該相同
        if (ns == nt)
          return s.substring(i + 1).equals(t.substring(i + 1));
        //如長度不同，那麼必須在s[i]插入t[i]，所以要保證s.substring(i).equals(t.substring(i + 1))
        else
          return s.substring(i).equals(t.substring(i + 1));
    return (ns + 1 == nt);
  }
}

好了，今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支持是我最大的動力 。