Reverse words in a sentence without using PHP functions

[Dota2]

Hi guys, I need help with this problem. I am stuck with this for a very long time. I want to reverse words in a sentence without using inbuilt string manipulation functions like explode,array_reverse, substring, etc. Any data structure like stack, can be used.

 

input: this is phpfreaks

 

expected o/p: phpfreaks is this

 

 

I managed to do this in C and I've tried the same logic in PHP, but unfortunately my code is going in infinite loop. Please help me, I am new to PHP.

 

Thanks in advance.

 

rwords.php

[scootstah]

That was kind of fun. Here's my take:

<?php

function reverseString($input)
{
    $currentWord = '';
    $words = array();

    for ($i = 0; $i < strlen($input); $i++) {
        if ($input[$i] == ' ') {
            $words[] = $currentWord;
            $currentWord = '';
            continue;
        }

        $currentWord .= $input[$i];

        if ($i == (strlen($input) - 1)) {
            $words[] = $currentWord;
        }
    }

    if (!empty($words)) {
        $reversed = array();

        for ($i = (count($words) - 1); $i >= 0; $i--) {
            $reversed[] = $words[$i];
        }

        $output = '';

        foreach ($reversed as $word) {
            $output .= $word . ' ';
        }

        return trim($output);
    }
}

$input = 'this is phpfreaks';
$output = reverseString($input);

echo "Input: $input<br />Output: $output";

Input: this is phpfreaks
Output: phpfreaks is this

Edited August 15, 2015 by scootstah

[requinix]

No string manipulation functions? No functions at all! Unfortunately it turned out much simpler than I thought it would.

$input = " this is  phpfreaks";
$output = "";

$word = "";
for ($i = 0; @$input[$i] != ""; $i++) {
	if ($input[$i] == " ") {
		$output = " " . $word . $output;
		$word = "";
	} else {
		$word = $word . $input[$i];
	}
}
$output = $word . $output;

echo "[{$output}]\n";

[phpfreaks  is this ]

[scootstah]

Damn, way to show me up req.

[requinix]

I wasn't trying to I wouldn't use my own code for real because it's not clear how it works. There's something to be said for code that's longer but easier to understand.

[Dota2]

thanks guys, it's working. Sorry, but I find it very difficult to understand  the code.  

 

The interviewer told me to do it in 10 mins and given hint to use a data structure. I wasn't able to solve this in 10 mins. I guess there must be some simple way to solve this fast.

[scootstah]

I have edited my solution with comments, hopefully this will help you understand it better.

function reverseString($input)
{
    // initialize the currentWord with an empty string
    $currentWord = '';

    // initialize the list of words
    $words = array();

    // loop over every character in the input string
    for ($i = 0; $i < strlen($input); $i++) {
        // check if the current character is a space
        if ($input[$i] == ' ') {
            // if the current character is a space, then we know
            // we have completed a word.
            // add the current word to the words list
            $words[] = $currentWord;

            // reset the current word, so that we can make the next one
            $currentWord = '';

            // break the loop and continue on the next iteration
            continue;
        }

        // append the current character to the current word
        $currentWord .= $input[$i];

        // if we have reached the end of the string,
        // we need to add the current word to the list of words.
        if ($i == (strlen($input) - 1)) {
            $words[] = $currentWord;
        }
    }

    // make sure that there is a list of words
    // just some quick error checking. if a string 
    // was provided with only spaces, we would not have any words
    if (!empty($words)) {
        // initialize the reverse list of words
        $reversed = array();

        // loop *BACKWARDS* over the list of words.
        for ($i = (count($words) - 1); $i >= 0; $i--) {
            // since we are starting at the end of the 
            // words list, and moving backwards to the beginning,
            // by appending the current word to the reversed array,
            // we will end up with the opposite of $words...
            // or, a reversed list of the words.
            $reversed[] = $words[$i];
        }

        // initialize the output string
        $output = '';

        // loop over the reversed array and build the output string
        // note that we could have skipped this step,
        // and just build the output in the previous for() loop.
        // but having the reversed array may help debugging or just
        // enable curious inspection.
        foreach ($reversed as $word) {
            $output .= $word . ' ';
        }

        // finally, return the output.
        return trim($output);
    }
}

In a nutshell, this is what is happening:

 

- Take input string, and loop over every character.

- Build a string with each character until a space is reached, in which case we add that string to a list of words.

- After we have fully iterated the input and built the list of words, we will loop over the list of words backwards. That means we start with the last index and move backwards towards the first index. By doing this, we can build a string or array of the words in reversed order.

 

EDIT: And requinix's approach is basically the same, just more condensed.

Edited August 15, 2015 by scootstah

[gizmola]

The key to requinix's ingenious solution is the use of the '@' error suppression operator.

 

 

for ($i = 0; @$input[$i] != ""; $i++) {

This allows him to for-loop character by character through the input by treating the string as a character array, and then by reading beyond the end of the string. That allows him to avoid the use of the strlen() built-in used by Scootsah.

 

From there it's just concatenating the strings he finds in reverse order. Nice!

 

With that said, I think what they wanted you to do was use a stack, given the way the question was posed. An array works pretty well for this, so Scootsah's solution is basically what I think they expected.

 

He reads the words and adds them to the array using "$array[] = $word". You get a numerically ordered "stack".

 

Then it's just a matter of for looping through the array in reverse order.

 

So just for fun, here's a way you could walk through the array in reverse order without using a negative for loop to duplicate the array into a reversed form, based on Scootsah's solution:

 

<?php

function reverseString($input)
{
    $currentWord = '';
    $words = array();

    for ($i = 0; $i < strlen($input); $i++) {
        if ($input[$i] == ' ') {
            $words[] = $currentWord;
            $currentWord = '';
            continue;
        }

        $currentWord .= $input[$i];

        if ($i == (strlen($input) - 1)) {
            $words[] = $currentWord;
        }
    }

    if (!empty($words)) {
        $output = '';

	for (end($words); key($words) !== null; prev($words)) {
  		$output .= current($words) . ' ';
	}
        return trim($output);
    }
}

$input = 'this is phpfreaks';
$output = reverseString($input);

echo "Input: $input<br />Output: $output";

[Dota2]

Thanks a lot scootstah and gizmola for explaining the code so well. This makes much more sense now.

 

once again, thanks!!