題目
You are given two strings
word1andword2. Merge the strings by adding letters in alternating order, starting withword1. If a string is longer than the other, append the additional letters onto the end of the merged string.Return the merged string.
要求合併兩個字串，word2[i] 要接到 word1[i] 後面。如果某邊字元不夠，另一個變數就都放進去。
測資
測資一
+ Input: word1 = "abc", word2 = "pqr"
+ Output: "apbqcr"
- Explanation: The merged string will be merged as so:
- word1: a b c
- word2: p q r
- merged: a p b q c r測資二
+ Input: word1 = "ab", word2 = "pqrs"
+ Output: "apbqrs"
- Explanation: Notice that as word2 is longer, "rs" is appended to the end.
- word1: a b
- word2: p q r s
- merged: a p b q r s測資三
+ Input: word1 = "abcd", word2 = "pq"
+ Output: "apbqcd"
- Explanation: Notice that as word1 is longer, "cd" is appended to the end.
- word1: a b c d
- word2: p q
- merged: a p b q c d第一種寫法
class Solution {
public String mergeAlternately(String word1, String word2) {
char[] word1_cp = word1.toCharArray();
char[] word2_cp = word2.toCharArray();
String str = "";
int legth = 0;
// 找出最長的
if (word1_cp.length < word2_cp.length) {
legth = word2_cp.length;
} else {
legth = word1_cp.length;
}
// 開始合併
for (int i = 0; i < legth; i++) {
// 範圍以內
if (i < word1_cp.length && i < word2_cp.length) {
str += word1_cp[i];
str += word2_cp[i];
} else if (i > word1_cp.length - 1) {
// word1 比較短
str += word2_cp[i];
} else if (i > word2_cp.length - 1) {
// word2 比較短
str += word1_cp[i];
}
}
return str;
}
}但是這種暴力解寫法不太好，效能執行過於緩慢。
時間複雜度: O(n+m) 空間複雜度: O(n+m)
第二種寫法
class Solution {
public String mergeAlternately(String word1, String word2) {
StringBuilder result = new StringBuilder();
int i = 0;
// 在範圍裡面
while (i < word1.length() || i < word2.length()){
// 如果在 word1 範圍裡面
if (i < word1.length()){
result.append(word1.charAt(i));
}
// 如果在 word2 範圍裡面
if (i < word2.length()){
result.append(word2.charAt(i));
}
// 不能寫成 if-else 的原因是因為如果第一個 if 判斷成功了，就不會進入到 else 裡面。
// 但題目要求是 word1 比對完要進去 word2 比對，兩兩都要放進去。
i++;
}
return result.toString();
}
}時間複雜度: O(n+m) 空間複雜度: O(n+m)
雖然時間複雜度和空間複雜度和第一個版本寫的是一樣的，在 LeetCode 執行起來，第一版執行時間是 4ms，第二版執行時間是 1ms。第二版本明顯優於第一版本，原因在於第一個版本宣告了四個變數，且 String 在 Java 當中是不可變的（immutable），每一次的變動，都是在建立一個新的物件，然後回收前一個物件，因此每一次都是在建立一個新的記憶體空間及位置。
而 StringBuilder 是可變的（mutable），底層是實作 char[]，每次增減都不會重新建立一個新的物件。
第二種寫法是先將 index 鎖在 max(word1.length(), word2.length())，再分別把範圍設在 word1.length() 和 word2.length() 裡面。需要注意的是，這裡不能寫成 if-else，是因為如果 if 執行了，則不會執行 else，因此必須分開寫。
相關文章
留言
載入中…