题目

Codewar Consecutive strings

You are given an array(list) strarr of strings and an integer k. Your task is to return the first longest string consisting of k consecutive strings taken in the array. n being the length of the string array, if n = 0 or k > n or k <= 0 return "" (return Nothing in Elm, “nothing” in Erlang).

提供了字符串列表和整形 k。要得到连续 k 个字符串连接后的最长字符串，并返回它。
而当列表长度为零或 k 大于列表长度又或 k 小于等于 0 时返回空字符串。

例子:

strarr = [“tree”, “foling”, “trashy”, “blue”, “abcdef”, “uvwxyz”], k = 2

Concatenate the consecutive strings of strarr by 2, we get:

treefoling (length 10) concatenation of strarr[0] and strarr[1]
folingtrashy (" 12) concatenation of strarr[1] and strarr[2]
trashyblue (" 10) concatenation of strarr[2] and strarr[3]
blueabcdef (" 10) concatenation of strarr[3] and strarr[4]
abcdefuvwxyz (" 12) concatenation of strarr[4] and strarr[5]

Two strings are the longest: “folingtrashy” and “abcdefuvwxyz”.
The first that came is “folingtrashy” so
longest_consec(strarr, 2) should return “folingtrashy”.

In the same way:
longest_consec([“zone”, “abigail”, “theta”, “form”, “libe”, “zas”, “theta”, “abigail”], 2) –> “abigailtheta”

1
2
3
4
5
6
7
8

#include <string>
#include <vector>

class LongestConsec
{
public:
    static std::string longestConsec(const std::vector<std::string> &strarr, int k);
};

题解

首先需要理解题目意思。因为没有理解题目意思，我花费了一个多小时在去重和排序上，结果一直过不去。
是我想太多了……其实原来是那么简单！！！
首先，需要的是连接后的连续最长字符串。问题在于这个连接，连接是按列表顺序一个一个链接的，不需要考虑哪个元素最长，只需要考虑依次链接后第一次出现的最长字符串。
顺着这个思路开始写代码吧：

题目有说返回空字符串的条件:

n being the length of the string array, if n = 0 or k > n or k <= 0 return "" (return Nothing in Elm, “nothing” in Erlang).

那么我们可以先创建一个整形变量用于存储列表长度顺便与 k 进行比较。

1
2

unsigned long n = strarr.size();
if (n == 0 || k > n || k <= 0) return "";

接下来使用双循环依次链接字符串并进行比较。
要先创建一个字符串用于保存最大字符串。
接着是第一层循环。因为是连续字符串，因而只需要从左到右遍历一遍列表即可。关键在于遍历中止的地方，因为我们要链接字符串，因而不能超过第 strarr.size() - k 个字符串再进行链接，这样当后面字符串想链接结果超过了，就会指向一个虚无的地方，也就是空指针。这样会引发不可预测的情况。

1
2

std::string longest;
for (unsigned long i = 0; i <= n - k; i++) {

在这之后进行依次的字符串链接操作，需要一个字符串存储每次链接的字符串方便之后进行比较。而比较也非常简单，当该字符串大于原本最大的字符串 longest 就用 current 替换 longest 即可：
current 要在链接之前进行声明，这样才能在每次链接之前清空 current。

1
2
3
4
5

std::string current;
for (unsigned long j = 0; j < k; j++) {
    current += strarr[i + j];
}
if (current.length() > longest.length()) longest = current;

在循环之后返回的 longest 就是题目所需要的。
完整代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <string>
#include <vector>

class LongestConsec {
   public:
    static std::string longestConsec(const std::vector<std::string> &strarr,
                                     int k) {
        unsigned long n = strarr.size();
        if (n == 0 || k > n || k <= 0) return "";

        std::string longest;
        for (unsigned long i = 0; i <= n - k; i++) {
            std::string current;
            for (unsigned long j = 0; j < k; j++) {
                current += strarr[i + j];
            }
            if (current.length() > longest.length()) longest = current;
        }
        return longest;
    }
};