字符串的最小长度(C++)

Question

给定一个字符串S(可以包含多个单词)，你需要找到长度最小的单词。注：如果多个单词的长度相同，那么答案将是字符串中第一个长度最小的单词。

Input Format :
String S
Output Format :
Minimum length word
Constraints :
1 <= Length of String S <= 10^5
Sample Input 1 :
this is test string
Sample Output 1 :
is
Sample Input 2 :
abc de ghihjk a uvw h j
Sample Output 2 :
a

请检查有什么问题。输出中什么都没有。

下面是代码。

   /* input - Input String
*  output - Save the result in the output array (passed as argument). You don’t have to 
*  print or return the result
*/

int length(char input[], int si, int ei){
    int len = 0;
    for(int i = si; i <= ei; i++){
        len++;
    }
    return len;

}

char getString(char input[], int index){
    return input[index];
}

void minLengthWord(char input[], char output[]){
    int prev = -1;
    int i = 0;
    int minLength = 0, len = 0;
    int si, ei;
    for(; input[i] != '\0'; i++){
        if(input[i] == ' '){
            int len = length(input, prev + 1, i - 1);
            if(len > minLength){
                minLength = len;
                si = prev + 1;
                ei = i - 1;
            }
            prev = i;
        }

    }
    length(input, prev + 1, i - 1);
    if(len > minLength){
                minLength = len;
                si = prev + 1;
                ei = i - 1;
            }
    for(int i = 0; i < minLength; i++){
         output[i] = getString(input, si + i);
    }


    // Write your code here 

}

Answer 1

其实这是一道关于测试标准C字符串函数知识的作业。

题目中显示的代码不合理。

例如在函数 length

int length(char input[], int si, int ei){
    int len = 0;
    for(int i = si; i <= ei; i++){
        len++;
    }
    return len;

}

参数 input 不被使用。函数中的循环是多余的。该函数可以定义得更简单，比如

int length( int si, int ei )
{
    return ei - si + 1;
}

或在函数中 minLengthWord 这句话

        if(len > minLength){
            minLength = len;

确定字的最大长度而不是最小长度。

定义该函数的最好方法是当它返回给定字符串中最小字的位置和长度时，以这样的方式定义它。有了这样的信息，如果需要的话，你总是可以很容易地提取出最小词。

下面是一个演示程序。

#include <iostream>
#include <utility>
#include <cstring>

std::pair<size_t, size_t> minimum_word( const char *s, const char *delim = " \t" )
{
    std::pair<size_t, size_t> min = { 0, 0 };

    size_t i = 0;
    while ( *( s + i ) )
    {
        i += std::strspn( s + i, delim );

        if ( *( s + i ) )
        {
            size_t n = std::strcspn( s + i, delim );

            if ( min.second == 0 || n < min.second  )
            {
                min.first  = i;
                min.second = n;
            }

            i += n;
        }
    }

    if ( min.second == 0 ) min.first = i;

    return min;
}

int main() 
{
    const char *s = "Hello John Bradely";

    auto min = minimum_word( s );

    std::cout << "The minimum word is "; 
    std::cout.write( s + min.first, min.second ) << '\n';

    return 0;
}

程序的输出是

The minimum word is John

很容易改变所示函数的方式，使其返回一个动态创建的数组，其中最小的字将被复制。

#include <iostream>
#include <utility>
#include <cstring>

char * minimum_word( const char *s, const char *delim = " \t" )
{
    std::pair<size_t, size_t> min = { 0, 0 };

    size_t i = 0;
    while ( *( s + i ) )
    {
        i += std::strspn( s + i, delim );

        if ( *( s + i ) )
        {
            size_t n = std::strcspn( s + i, delim );

            if ( min.second == 0 || n < min.second  )
            {
                min.first  = i;
                min.second = n;
            }

            i += n;
        }
    }

    if ( min.second == 0 ) min.first = i;

    char *word = new char[min.second + 1]();

    std::memcpy( word, s + min.first, min.second );

    return word;
}

int main() 
{
    const char *s = "Hello John Bradely";

    char *word = minimum_word( s );


    std::cout << "The minimum word is " << word << '\n'; 

    delete [] word;

    return 0;
}

程序的输出是

The minimum word is John