Reverse a Word.

#string #array #twopointers #algorithm

I wrote couple of posts previously here and here on how to find duplicates in an array and we saw different variety of that problem. I want to switch gear now to string related problems. Previous posts on arrays built a good foundation for us to solve string related problem because string is an essentially an array of characters.

We are given a word which contains only alphabetical characters. Considering string is an array of characters and one of the biggest advantage and vital key to solve certain array problems is to iterate an array from forwards and backwards at the same time.

We can use two pointers where one pointer start from beginning and other pointer move inwards from end of the array.

This information is vital to solve this problem. Let’s use that algorithm and write down code.

Could we use the same algorithm to reverse words inside a sentence? e.g. "This is a word" should change into "word a is This" by the algorithm.
If we split the string by a whitespace we'll get an array of strings and then we can use above algorithm to reverse a sentence.

Another problem where we could utilize same algorithm is to solve string palindrome problem. A word is a palindrome when it reads same from backwards as forward e.g. kayak, noon etc.

Now we know that we can traverse a string from forwards and backwards, we can use that knowledge to solve palindrome problem.

This is it for this post. I plan to write more on string related problems in my next posts.

Stay tuned. :)

Top comments (8)

dallgoot • Jul 26 '18

very , very small optimization :p

public static boolean isPalindrome(String input)
{
    char[] charArray = input.toCharArray();
    int cursor = 0;
    int max = input.length() - 1;

    while(cursor <= max && charArray[cursor] == charArray[max-cursor])
    {
        cursor++;
    }
    return cursor > max; 
}

if by any chance you can benchmark the 2 versions : me very glad ;)

caubeen • Jul 26 '18 • Edited

JavaScript!!

const palindrome = string => [...string].reverse().join('') === string

Justin • Jul 26 '18

Go! This was a fun challenge as I'm fairly new to Go =) Feedback is welcomed!

package main

import (
    "fmt"
    "os"
    "strings"
)

func main() {
    var phraseList = os.Args[1:]
    for index := range phraseList {
        fmt.Printf("%s :: %s :: %t\n",
            phraseList[index],
            reverse(phraseList[index]),
            isPalindrome(phraseList[index]))
    }
}

func reverse(phrase string) string {
    var phraseBytes = []byte(phrase)
    var phraseLenght = len(phraseBytes) - 1
    var tempChar byte
    for index := 0; index < len(phraseBytes)/2; index++ {
        tempChar = phraseBytes[index]
        phraseBytes[index] = phraseBytes[phraseLenght-index]
        phraseBytes[phraseLenght-index] = tempChar
    }
    return string(phraseBytes)
}

func isPalindrome(phrase string) bool {
    return strings.Replace(phrase, " ", "", -1) ==
        strings.Replace(reverse(phrase), " ", "", -1)
}

C:\go\src\reverse> .\reverse reverse four three "taco cat"
reverse :: esrever :: false
four :: ruof :: false
three :: eerht :: false
taco cat :: tac ocat :: true

Mohamad • Jul 25 '18

Python!!

def palindrome(string):
    return all(string[i] == string[-i-1] for i in range(len(string)//2))

Christopher McClellan • Jul 26 '18

Here’s a challenge for you. You wrote the same loop twice. Could you write a function that takes an anonymous function as an arg so you never have to write this “dual ended” loop again?