Find longest word in a string: are any of these algorithms good? [closed]

Question

I'm trying to find the longest word in a given text, but it has to be done "old school": without using split, enumerate, etc. (I'm using Python but what I'm looking for is more of a pseudocode or a general algorithm). I'm struggling with the last word (or the last character).

As a precondition, there are no leading or trailing spaces.

So I came up with two options that do the job but I feel like they're breaking some best practices:

Option 1

longestWord=""
lenlongestWord=0
currentWord=""
for i in range(len(text)):
    if text[i]==" " or i==len(text)-1:
        if i==len(text)-1:
            currentWord+=text[i]
        if len(currentWord) > lenlongestWord:
            longestWord=currentWord
            lenlongestWord=len(currentWord)
        currentWord=""
    else:
        currentWord+=text[i]
print("Longest word: ", longestWord)

From this one I dislike this part (but I had to do it or I would be missing the last word in the string:

if i==len(text)-1:
    currentWord+=text[i]

because I'm duplicating the concatenation, both in the "if" block and the "else" block.

Option 2:

text+=" "
longestWord=""
lenlongestWord=0
currentWord=""
for i in range(len(text)):
    if text[i]==" ":
        if len(currentWord) > lenlongestWord:
            longestWord=currentWord
            lenlongestWord=len(currentWord)
        currentWord=""
    else:
        currentWord+=text[i]
print("Longest word: ", longestWord)

What I don't like from this one is the fact that I'm manipulating the original text by adding a trailing whitespace so I can read it as a word separator.

Is there a third option I'm missing? Or maybe one of these two is not as bad practice as I believe?

Answer 1

String concatenation can be slow. If you just want to go "old school", and speed is important, then forget storing the current word, and continually concatenating letters onto it.

Just store the start of the current word, as an index into the array, and the start of the longest word. Store the length of the current word, and the length of the longest.

Whenever the length of the current word exceeds the length of the (previous) longest, update the start and length of the longest.

At the end, you will have the start index and length of the longest word. You can just extract that word from the string.

PS: There's an assumption in your code that words are always separated by spaces, and that there's no other form of punctuation. Is this deliberate?

Answer 2

If you feel like trying recursion, you could give this a go. This is by no means elegant, and it does assume that your string is separated by a single space between words, but it's pretty quick. Other considerations you'll need to take into account is how you break ties (in this case, unless a word is strictly longer, it goes with the first one it finds). I've also built a helper function to recursively build the next word in the string.

def buildWord(string):
  if(len(string) == 0 or string[0]==' '):
    return "";
  else:
    return string[0] + buildWord(string[1:]);

def findLongest(string, word = ""):
  #stop if the string is empty
  if(len(string) <= 0):
    return word;
  #build the next word in the string
  curWord = buildWord(string);
  #check the current longest word    
  longestWord = curWord if len(curWord) > len(word) else word;
  #keep checking
  return findLongest(string[len(curWord)+1:], longestWord);

print(findLongest("this is a string with a very long antediluvian word in it"));

Answer 3

How about the straightforward approach?

string = 'abc defg hij klm ytrda nopasdas'

st, n = 0, 0 # start and length of longest word
m = 0        # start of current word

# instead of enumerate, you can just increment i in the loop
for i, x in enumerate(string): 
    if x == ' ':
        if i > m+n:
            st = m
            n = i-st
        m = i+1

# this is the special case for the last word
if i > m+n:
    st = m
    n = i-st+1

print(string[st:st+n])

This will not copy strings and only go through your string once. If you did this in C you would probably use pointers. For C++ you would use iterators - sadly, in Python, these are not as powerful.