Reverse Words In String [asked by 🚖 Bolt]

Hello👋,
My name is Alex and I'm maker of Devmates.co. 😊

We are resolving daily coding problems which asked by top tech companies together. We share our solutions, give some help if anyone stuck, support each other and just hangout together in the internet. 🍻☕️💬

I get this problem from our members or just searching them in the internet(leetcode forums, Glassdoor, teamblind, etc.). Sometimes this problem can be very easy, sometimes too 👷‍♂️hard, everything depends on skills but we are trying to resolve all of them and Have Fun. 🙌

Today I want to share problem which was asked by Bolt (🚖 Taxify).

Feel free to share you solutions in comments. I would love to find "better" solution and put it to the article.😉

Problem:

Reverse each word in a given string.

You can't use language provided methods (such as split, reverse, etc.)

Example

__Input:__ 'hello this is devmates'
__Output:__ 'olleh siht si setamved'

Solution:

The idea is simple - iterate over the string and check all characters:

• If current character is space then add it to our result string.
• If current character is not space then we should start accumulate it to our temporary string.

Let's start from iterating over the string

function reverseWordsInString(str){
        let result = '';
        for (let i = 0; i < str.length; i++){
          // here we should check is it space or not
          // if not then we should iterate over the current word
        }
        return result;
    }

We can use while statement for iterate over the word. Also we are using the same index i, so we will not iterate over the same word twice. If current character is space ' ' then we should add it directly to our result.

function reverseWordsInString(str){
        let result = '';
        for (let i = 0; i < str.length; i++) {
          if (str[i] !== ' '){
            while(str[i] !== ' ' && i < str.length){
              // here we can iterate over the current word.
              i++;
            }
          } else {
            result += str[i];
          }
        }
        return result;
    }

Let's accumulate our word to tmp variable in reverse order and save it to result.

function reverseWordsInString(str){
        let result = '';
        for (let i = 0; i < str.length; i++) {
          let tmp = '';
          if (str[i] !== ' '){
            while(str[i] !== ' ' && i < str.length){
              tmp = str[i] + tmp;
              i++;
            }
            result += tmp + (str[i] ? str[i] : '');
          } else {
            result += str[i];
          }
        }
        return result;
    }

This solution is not good because of we are using the same index in two loops. How we can optimize it? - use only 1 loop. Also we can use the function for identify is current character is separator or not. It give as opportunity to add more separators if needed.

Optimized Solution

      function reverseWordsInString (phrase) {
          let result = "";
          let reversed_word = "";
          for (let i = 0; i < phrase.length; i++) {
              if (isSeparator(phrase[i])) {
                  result += reversed_word;
                  result += phrase[i];
                  reversed_word = "";
              } else {
                  reversed_word = phrase[i] + reversed_word;
              }
          }

          if (reversed_word.length > 0){
               result += reversed_word;
          }

          return result;
      }

      function isSeparator(symbol){
          switch (symbol) {
              case ' ':
                  return true;
              default:
                  return false;
          }
      }

      module.exports = reverseWordsInString;

Now we can test it. Let's write some tests to our solution using Jest.

// /../someFile.js
      function reverseWordsInString (phrase) {
          let result = "";
          let reversed_word = "";
          for (let i = 0; i < phrase.length; i++) {
              if (isSeparator(phrase[i])) {
                  result += reversed_word;
                  result += phrase[i];
                  reversed_word = "";
              } else {
                  reversed_word = phrase[i] + reversed_word;
              }
          }

          if (reversed_word.length > 0){
               result += reversed_word;
          }

          return result;
      }

      function isSeparator(symbol){
          switch (symbol) {
              case ' ':
                  return true;
              default:
                  return false;
          }
      }

      module.exports = reverseWordsInString;

// /../someFile.test.js
    let reverseWordsInString = require('./someFile.js');


    test('Empty string', ()=>{
      expect(reverseWordsInString("")).toBe("")
    });

    test('One word', ()=>{
      expect(reverseWordsInString("hello")).toBe("olleh")
    });

    test('Valid string with single spaces', ()=>{
      expect(reverseWordsInString('hello this is devmates!')).toBe('olleh siht si !setamved')
    });

    test('Only spaces in string', ()=>{
      expect(reverseWordsInString("    ")).toBe("    ")
    });

    test('Multiply Spaces at the beginning in given string', ()=>{
      expect(reverseWordsInString("   hello this is devmates!")).toBe("   olleh siht si !setamved")
    });

    test('Multiply Spaces at the end in given string', ()=>{
      expect(reverseWordsInString("hello this is devmates!  ")).toBe("olleh siht si !setamved  ")
    });

    test('Multiply spaces at the beginning and at the end in given string', ()=>{
      expect(reverseWordsInString("  hello this is devmates!   ")).toBe("  olleh siht si !setamved   ")
    });

    test('Multiply spaces everywhere in given string', ()=>{
      expect(reverseWordsInString("   hello    this     is devmates  ")).toBe("   olleh    siht     si setamved  ")
    });

Thanks for reading.🙌

Hope you like it. I'll share some of our problems with solutions here. Also you can join us at Devmates.co and don't miss any problems.💪

If you have any other solutions(e.g. do it in-place) - share it in comments.💬

Good Luck and Have Fun😉

Comments

[J]

Hi Alex,
I appreciate your efforts and wanna add a suggestion. It would be great if you can also mention the time & space complexities for your solution coz the interviewers generally ask.
Cheers!

[Alex Wawl 🐼]

Thanks !! I'll do it in my next solutions!!