5ms solution without String.split()


  • 0
    A

    Classic task that is solved using two reverses:

    1. reverse of the whole string
    2. reverse of each word in reversed string

    If there were no extra whitespaces, this all would be "in-place" for the char[] array produced from the incoming string and result would be returned as the String made from this array.

    As we have extra whitespaces, we need to create new char[] array or StringBuilder and write reversed words there ignoring other whitespaces.

    Code is not that concise as solutions with split, but shows just another way to solve the problem.

       public String reverseWords(String s) {
            if (s == null) return null;
            
            char[] ch = s.toCharArray();
            int n = ch.length;
            
            // Reverse the whole array
            int lo = 0, hi = n - 1;
            while (lo < hi) swap(ch, lo++, hi--);
            
            // Reverse each world in result
            hi = 0;
            StringBuilder sb = new StringBuilder();
            while (hi < n) {
                while (hi < n && ch[hi] == ' ') hi++;
                while (hi < n && ch[hi] != ' ') hi++;
                
                int h = hi - 1;
                if (ch[h] == ' ') break;
                while (h >= 0 && ch[h] != ' ') sb.append(ch[h--]);
                sb.append(' ');
            }
            if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
            
            return sb.toString();
        }
        private void swap(char[] ch, int lo, int hi) {
            char t = ch[lo];
            ch[lo] = ch[hi];
            ch[hi] = t;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.