decode string

string serialization

word abbr

string decode

Reverse Words in a String II

• the sky is blue -> blue is sky the
• does not contain trailing or leading space

public class Solution {
    public void reverseWords(char[] s) {
        int start = 0;
        int end = 0;

        while(end < s.length){
            while(end < s.length && s[end] != ' ') end++;

            reverse(s, start, end - 1);

            end ++;
            start = end;
        }

        reverse(s, 0, s.length - 1);
    }

    private void reverse(char[] s, int start, int end){
        while(start < end){
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;

            start ++;
            end --;
        }
    }
}

Reverse Words in a String

• may contain trailing or leading space

public class Solution {
    public String reverseWords(String s) {
        if(s.length() == 0) return "";
        int start = 0;
        int end = 0;

        char[] array = s.toCharArray();

        while(end < s.length()){
            while(end < s.length() && array[end] == ' ') end ++;
            start = end;
            while(end < s.length() && array[end] != ' ') end ++;
            reverse(array, start, end - 1);
        }

        StringBuilder sb = new StringBuilder();
        end = s.length() - 1;

        while(end >= 0){
            while(end >= 0 && array[end] == ' ') end --;
            while(end >= 0 && array[end] != ' '){
                sb.append(array[end--]);
            }
            sb.append(' ');
        }

        return sb.toString().trim();
    }

    private void reverse(char[] s, int start, int end){
        while(start < end){
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;

            start ++;
            end --;
        }
    }
}

rotated array

• 1,2,3,4,5,6,7 -> 5,6,7,1,2,3,4

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;

        reverse(nums, 0, nums.length - k - 1);
        reverse(nums, nums.length - k, nums.length - 1);
        reverse(nums, 0 , nums.length - 1);
    }

    private void reverse(int[] nums, int start, int end){
        while(start < end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;

            start ++;
            end --;
        }
    }
}

valid palindrome:

• can not use: while(start < end && s.charAt(start) == s.charAt(end)) because, space may exist in the middle which in this problem can be deemed as valid.

public class Solution {
    public boolean isPalindrome(String s) {
        if(s.length() <= 1) return true;
        s = s.toLowerCase();

        int start = 0;
        int end = s.length() - 1;

        while(start < end){
            while(start < end && !Character.isLetterOrDigit(s.charAt(start)))
                start ++;
            while(start < end && !Character.isLetterOrDigit(s.charAt(end)))
                end --;

            if (s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }

        return true;
    }
}

• naive

int start = 0;
int end = s.length() - 1;

while (start < end) {
    if (s.charAt(start) != s.charAt(end)) return false;
    start++;
    end--;
}

return true;