【LeetCode】1768.交替合并字符串


一、问题

给你两个字符串 word1word2 。请你从 word1 开始,通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长,就将多出来的字母追加到合并后字符串的末尾。返回合并后的字符串 。

二、解题思路

1.双指针

1)i,j分别指向字符串word1,word2;
2)循环遍历word1,word2,只要i,j均遍历完成

2.单指针

其实,只要一个指针就可以搞定,而且遍历次数最多Math.min(word1 的长度, word2 的长度),剩下的最长那个字符串,利用String.substring(index)即可得到需要的答案。伪代码如下:

while(i<minLength){
	sb.append(word1[i]);
	sb.append(word2[i]);
	i++;
}
if(i<word1.length()){
	sb.append(word1.substring(i));
}
if(i<word2.length()){
	sb.append(word2.substring(i));
}

三、代码

1.双指针

class Solution {
    public String mergeAlternately(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int i = 0;
        int j = 0;

        StringBuilder ans = new StringBuilder();
        while (i < m || j < n) {
            if (i < m) {
                ans.append(word1.charAt(i));
                ++i;
            }
            if (j < n) {
                ans.append(word2.charAt(j));
                ++j;
            }
        }
        return ans.toString();
    }
}
/**
作者:力扣官方题解
链接:https://leetcode.cn/problems/merge-strings-alternately/solutions/1913930/jiao-ti-he-bing-zi-fu-chuan-by-leetcode-ac4ih/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
*/

2.单指针

public String mergeAlternately(String word1, String word2) {
    int i=0;
    StringBuilder sb=new StringBuilder();
    int minLength=Math.min(word1.length(), word2.length());
    while(i<minLength){
        sb.append(word1.charAt(i));
        sb.append(word2.charAt(i));
        i++;
    }
    if(i<word1.length()){
        sb.append(word1.substring(i));
    }
    if(i<word2.length()){
        sb.append(word2.substring(i));
    }
    return sb.toString();
}  

复杂度分析

  • 时间复杂度:O(m+n),其中 m 和 n 分别是字符串 word1 和 word2 的长度。

  • 空间复杂度:O(1)或 O(m+n)。如果使用的语言支持可修改的字符串,那么空间复杂度为 O(1),否则为 O(m+n),比如java。注意这里不计入返回值需要的空间。


文章作者: Kezade
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Kezade !
评论
  目录