資訊專欄INFORMATION COLUMN
摘要：復雜度思路考慮如果兩個字符串的長度，是肯定當兩個字符串中有不同的字符出現的時候，說明之后的字符串一定要相等。的長度比較大的時候，說明的時候，才能保證距離為。
LeetCode[161] One Edit Distance
StringGiven two strings S and T, determine if they are both one edit distance apart.
復雜度
O(N),O(1)
思路
考慮如果兩個字符串的長度 > 1，是肯定return false;
當兩個字符串中有不同的字符出現的時候，說明之后的字符串一定要相等。
abc ac
s的長度比較大的時候，說明s.substring(i + 1).equals(t.substring(i))的時候，才能保證距離為1。
ac abc
t的長度比較大的時候，說明t.substring(i + 1).equals(s.substring(i)), 才能保證距離為1。
abe ace
當剩下的字符串距離相等的時候，說明只有當剩下的字符串相等的時候，才能保證距離為1.
代碼
public boolean isOneEditDistance(String s, String t) {
for(int i = 0;i < Math.min(s.length(), t.length()); i ++) {
if(s.charAt(i) != t.charAt(i)) {
if(s.length() == t.length()) {
return s.substring(i + 1).equals(t.substring(i + 1));
}
else if(s.length() > t.length()) {
return s.substring(i + 1).equals(t.substring(i));
}
else {
return s.substring(i).equals(t.substring(i + 1));
}
}
}
return Math.abs(s.length(), t.length()) == 1;
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66139.html
摘要：比較長度法復雜度時間空間思路雖然我們可以用的解法，看是否為，但中會超時。這里我們可以利用只有一個不同的特點在時間內完成。 One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. 比較長度法 復雜度 時間 O(N) 空間 O(1) 思路 雖然我們可以用...
摘要：復雜度思路考慮用二維來表示變換的情況。如果兩個字符串中的字符相等，那么如果兩個字符串中的字符不相等，那么考慮不同的情況表示的是，從字符串到的位置轉換到字符串到的位置，所需要的最少步數。 LeetCode[72] Edit Distance Given two words word1 and word2, find the minimum number of steps require...
摘要：動態規劃復雜度時間空間思路這是算法導論中經典的一道動態規劃的題。 Edit Distance Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You h...
摘要：構造數組，是的，是的，是將位的轉換成位的需要的步數。初始化和為到它們各自的距離，然后兩次循環和即可。 Problem Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 s...
摘要：題目要求輸入兩個字符串和，允許對進行插入，刪除和替換的操作，計算出將轉化為所需要的最少的操作數。其中存儲的是轉換為的最小步數。首先從邊緣情況開始考慮。只要在此基礎上再進行一次插入操作即可以完成轉換。 題目要求 Given two words word1 and word2, find the minimum number of steps required to convert wor...
閱讀 2337·2019-08-30 15:44
閱讀 1260·2019-08-30 13:01
閱讀 3307·2019-08-30 11:22
閱讀 3093·2019-08-29 15:23
閱讀 1614·2019-08-29 12:22
閱讀 3366·2019-08-26 13:58
閱讀 3439·2019-08-26 12:17
閱讀 3479·2019-08-26 12:16
