Dota2 Posted August 14, 2015 Share Posted August 14, 2015 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 Quote Link to comment Share on other sites More sharing options...
scootstah Posted August 15, 2015 Share Posted August 15, 2015 (edited) 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 1 Quote Link to comment Share on other sites More sharing options...
requinix Posted August 15, 2015 Share Posted August 15, 2015 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 ] 3 Quote Link to comment Share on other sites More sharing options...
scootstah Posted August 15, 2015 Share Posted August 15, 2015 Damn, way to show me up req. Quote Link to comment Share on other sites More sharing options...
requinix Posted August 15, 2015 Share Posted August 15, 2015 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. Quote Link to comment Share on other sites More sharing options...
Dota2 Posted August 15, 2015 Author Share Posted August 15, 2015 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. Quote Link to comment Share on other sites More sharing options...
Solution scootstah Posted August 15, 2015 Solution Share Posted August 15, 2015 (edited) 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 Quote Link to comment Share on other sites More sharing options...
gizmola Posted August 15, 2015 Share Posted August 15, 2015 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"; 1 Quote Link to comment Share on other sites More sharing options...
Dota2 Posted August 15, 2015 Author Share Posted August 15, 2015 Thanks a lot scootstah and gizmola for explaining the code so well. This makes much more sense now. once again, thanks!! Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.