151. Reverse Words in a String

Intuition¶

Image taken from: https://leetcode.com/problems/reverse-words-in-a-string/solutions/1531693/c-2-solutions-o-1-space-picture-explain-clean-concise/?envType=study-plan-v2&envId=top-interview-150

Approach¶

We will need to implement 3 sub-procedures for the above solution:

Reverse a string¶

Idea¶

Using two pointers, i and j:

• i at start of string
• j at end of string
  swap them while i < j

Code¶

public void reverse(char[] a, int i, int j) {  
  char temp;  
  while(i < j) {  
    temp = a[i];  
    a[i++] = a[j];  
    a[j--] = temp;  
  }  
}

Reverse a sub-string (a word inside a string)¶

Idea¶

Using two pointers, i and j:

• i should be start of substring
• j should be end of substring
  call reverse(i,j) on the substring

The hard part is skipping spaces in between words with i and j

Code¶

public void reverseWord(char[] a, int n) {  
  int i = 0;  
  int j = 0;  

  while(i < n) {  
    while(i < j || i < n && a[i] == ' ') i++;  
    while(j < i || j < n && a[j] != ' ') j++;  
    reverse(a,i,j-1);  
  }  
}

Clean up remaining spaces¶

Idea¶

Using two pointers, i and j:

• i should keep the end of previous word
• j should traverse until there is a word available
  Copy the word from j to i until there are spaces
  Add a single space for the copied word

Code¶

public String clean(char[] a, int n) {  
  int i = 0, j = 0;  

  while(j < n) {  
    while(j < n && a[j] == ' ') j++;  
    while(j < n && a[j] != ' ') a[i++] = a[j++];  
    while(j < n && a[j] == ' ') j++;  
    if(j < n) a[i++] = ' ';  
  }  

  return new String(a).substring(0,i);  
}

Comments