Finding the shortest word in a C string

Question

I'm trying to find the shortest word in a given C string, but somehow it fails if there is only one word or if it's the last word.

I tried start at the null character and count backwards until I hit " " and than count the steps I took but it did not work properly.

Also is there a better or faster way to iterate through a string while finding the shortest or longest word?

#include <sys/types.h>
#include <string.h>
#include <stdio.h>

ssize_t find_short(const char *s) {
    int min = 100; 
    int count = 0; 

    for (int i = 0 ; i < strlen(s); i++) {
        if (s[i] != ' ') {
            count++;   
        } else {
            if (count < min) {
                min = count; 
            }
            count = 0; 
        }
    
        if (s[i] == '\0') {
            count = 0;
            while (s[i] != ' ') {
                --i; 
                count++; 
                if (s[i] == ' ' && count < min) {
                    min = count;  
                }
            }
        }
    }
    return min; 
}

Answer 1

Your idea was correct you just complicated a little. Let us break down your code:

int min = 100; 

First you should initialized min to INT_MAX which you can get it from #include <limits.h>. Maybe all words are bigger than 100.

for (int i = 0 ; i < strlen(s); i++)

you can use the C-String terminal character '\0':

 for(int i = 0; s[i] != '\0'; i++)

The if and else part:

if (s[i] != ' ') 
     {
        count++;   
     }
     
    else
    {
      if (count < min)
       {
          min = count; 
       }
      count = 0; 
    }

almost correct, but you need to append count != 0 to the condition count < min to ensure that if the string starts with spaces, you do not want to count them as the smallest word.

This part can be removed :

 if (s[i] == '\0')
    { 
      count = 0;
       while(s[i] != ' ')
       {
         --i; 
         count++; 
         if(s[i] == ' ' && count < min) 
         {
           min = count;  
         }
        
       }
       
    }

check the last word outside the loop. Hence, your code would look like the following:

ssize_t find_short(const char *s)
{
    int min = INT_MAX;
    int count = 0; 
    // Iterate over the string  
    for(int i = 0; s[i] != '\0'; i++){
        if(s[i] != ' '){ // Increment the size of the word find so far
            count++;
        }
        else{ // There is a space meaning new word
            if(count != 0 && count < min){  // Check if current word is the smallest 
                min = count; // Update the counter
            }
            count = 0; // Set the counter 
        }
    } 
    return (count < min) ? count : min // Check the size of the last word
 }

Answer 2

There are multiple issues in your code:

• mixing int, size_t and ssize_t for the index and string lengths and return value is confusing and incorrect as these types have a different range.
• int min = 100; produces an incorrect return value if the shortest word is longer than that.
• for (int i = 0 ; i < strlen(s); i++) is potentially very inefficient as the string length may be recomputed at every iteration. for (size_t i = 0 ; s[i] != '\0'; i++) is a better alternative.
• find_short returns 100 for the empty string instead of 0.

Scanning backwards from the end is tricky and not necessary: to avoid this special case, omit the test in the for loop and detect the end of word by comparing the character with space or the null byte, breaking from the loop in the latter case after potentially updating the minimum length.

The initial value for min should be 0 to account for the case where the string is empty or contains only whitespace. Whenever a word has been found, min should be updated if it is 0 or if the word length is non zero and less than min.

Here are an implementation using <ctype.h> to test for whitespace:

#include <stddef.h>
#include <ctype.h>

size_t find_short(const char *s) {
    size_t min = 0, len = 0;

    for (;;) {
        unsigned char c = *s++;
        if (isspace(c) || c == '\0') {
            if (min == 0 || (len > 0 && len < min))
                min = len;
            if (c == '\0')  // test for loop termination
                break;
            len = 0;
        } else {
            len++;   
        }
    }
    return min; 
}

Here is a more general alternative using the functions strcspn() and strspn() from <string.h> where you can define the set of word separators:

#include <string.h>

size_t find_short(const char *s) {
    size_t min = 0;
    const char *seps = " \t\r\n";  // you could add dashes and punctuation

    while (*s) {
        s += strspn(s, seps);
        if (*s) {
            size_t len = strcspn(s, seps);
            if (min == 0 || (len > 0 && len < min))
                min = len;
            s += len;
        }
    }
    return min; 
}

Answer 3

As you said your program fails if the shortest word is the last one. That's because the last i for which the loop runs is i == len-1 that is the last letter of the string. So in this last lap, count will be incremented, but you will never check if this count of the last word was smaller than the min you had so far.

Assuming that you receive a null-terminated string, you could extend the loop till i <= len (where len = strlen(s)) and adjust the if condition to

if( s[i] != ' ' && s[i] )

That means: if s[i] is not a space nor the terminating null character

Also you can remove the condition if (s[i] == '\0').

About faster algorithms, I don't think it's possible to do better.

If you want you can automate the count increment using an inner empty for loop running till it finds a space and then in the outer for check for how long the innermost have been running.

I once wrote a program for the same problem which uses an inner for, I show you just for the algorithm, but don't take example from the "style" of the code, I was trying to make it as few lines as possible and that's not a good practice.

ssize_t find_short(const char *s)
{
    ssize_t min = 99, i = 0;
  
    for( --s; !i || (min > 1 && *s); s += i) {
        for(i = 1; *(s+i) != ' ' && *(s+i); i++);
        if( min > i-1 ) min = i-1;
    }
  
    return min;
}

Oh, one improvement I just noticed in my code could be to return the min when it reaches 1 because you know you are not going to find shorter words.

Answer 4

I'd suggest that you use strtok to split your string into an array of strings using space character as the token. You can then process each string in the resulting array to determine which is the "word" that you want.

See Split strings into tokens and save them in an array