LeetCode-01-字符串交叉拼接

发表于 更新于 分类于 / 阅读次数： 本文字数： 557 阅读时长 ≈ 2 分钟

LeetCode算法题：字符串交叉拼接。

题目

LeetCode：LeetCode 75 - 学习计划-1-交替合并字符串

题目简述：给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回 合并后的字符串 。

  • 1 <= word1.length, word2.length <= 100
  • word1 和 word2 由小写英文字母组成

思路

从题干中可得到以下关键信息：

  • 两字符串不等长
  • 交替添加

因此推论出两个要点：

  • strlen计算输入字符串长度
  • 读取时可共用同一索引值/双指针

因此可根据输入字符串长度动态分配内存，随后循环读取两数组的元素。

  • malloc分配内存长度应为len1+len2+1，末尾存放’\0’;

代码

方案A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char* mergeAlternately(char* word1, char* word2) {
    assert(word1);
    assert(word2);
    int word1_len = strlen(word1);
    int word2_len = strlen(word2);
    int word_rd_idx = 0;
    int string_wr_idx = 0;
    char* string_out = (char*)malloc(sizeof(char) * (word1_len + word2_len + 1));
    while ((word_rd_idx < word1_len) || (word_rd_idx < word2_len))
    {
        word_rd_idx < word1_len ? (string_out[string_wr_idx++] = word1[word_rd_idx]) : 0;
        word_rd_idx < word2_len ? (string_out[string_wr_idx++] = word2[word_rd_idx]) : 0;
        word_rd_idx++;
    }
    string_out[string_wr_idx] = '\0';
    return string_out;
}

方案A中无论哪个字符串更长，while中均会判断两次。如果AB长度差异过大影响效率。

方案B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
char* mergeAlternately(char* word1, char* word2) {
    assert(word1);
    assert(word2);
    int word1_len = strlen(word1);
    int word2_len = strlen(word2);
    int word_rd_idx = 0;
    int string_wr_idx = 0;
    char* string_out = (char*)malloc(sizeof(char) * (word1_len + word2_len + 1));
    while ((word_rd_idx < word1_len) && (word_rd_idx < word2_len))
    {
        word_rd_idx < word1_len ? (string_out[string_wr_idx++] = word1[word_rd_idx]) : 0;
        word_rd_idx < word2_len ? (string_out[string_wr_idx++] = word2[word_rd_idx]) : 0;
        word_rd_idx++;
    } 
    if(word1_len>=word2_len)
    {
        while (word_rd_idx < word1_len)
        {
 			string_out[string_wr_idx++] = word1[word_rd_idx];
            word_rd_idx++;
        }
    }
    else
    {
        while (word_rd_idx < word2_len)
        {
 			string_out[string_wr_idx++] = word2[word_rd_idx];
            word_rd_idx++;
        }
    }
    string_out[string_wr_idx] = '\0';
    return string_out;
}

方案C

采用双指针，进一步减少定义变量的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char* mergeAlternately(char* word1, char* word2) {
    assert(word1);
    assert(word2);
    char *p = (char*)malloc(sizeof(char) * (strlen(word1) + strlen(word2) + 1));//起始指针
    char *string_out = p;//写入字符的移动指针
    while(*word1 && *word2)
    {
        *string_out++=*word1++;
        *string_out++=*word2++;
    }
    while(*word1)
    {
        *string_out++=*word1++;
    }
    while(*word2)
    {
        *string_out++=*word2++;
    }
    *string_out = '\0';
    return p;
}

复杂度

方案ABC的复杂度一致，时间复杂度为O(n+m):源于strlen(word1)与strlen(word2)。空间复杂度为O(n+m):源于malloc分配内存

————————— End —————————

“试玉要烧三日满，辨材须待七年期。”– 《放言五首·其三》