Leetcode. 165. Compare Version Numbers

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

Analysis:

We can split the string to be a string array and then compare them separately. During comparison, it may happen that the two arrays are not the same size. Then we need to go through the longest one and add 0 if one is less than the longest size.

Note: here split function using on . we can not use . directly, but use \\.

Time complexity: O(n)
Space complexity: O(n)

Code is below:

public class Solution {
    public int compareVersion(String version1, String version2) {
        // O(n) O(n)
        
        if (version1 == null || version2 == null) {
            return 0;
        }
        
        if (version1.equals(version2)) {
            return 0;
        }
        
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        
        int maxLen = Math.max(v1.length, v2.length);
        
        for (int i = 0; i < maxLen; i++) {
            int num1 = i < v1.length ? Integer.parseInt(v1[i]) : 0;
            int num2 = i < v2.length ? Integer.parseInt(v2[i]) : 0;
            
            if (num1 < num2) {                 return -1;             }                          if (num1 > num2) {
                return 1;
            }
        }
        
        return 0;
    }
}

Leetcode 151 & 186. Reverse Words in a String I& II

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Analysis:

Use extra place. To split the whole string and get a string array, then go from the back and put them in a new string.

Time complexity : O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public String reverseWords(String s) {
        // O(n) O(n)
        
        if (s == null || s.length() == 0) {
            return "";
        }
        
        s = s.trim();
        String[] str = s.split(" ");
        StringBuilder sb = new StringBuilder();
        
        for (int i = str.length - 1; i >= 0; i--) {
            if (!str[i].equals("")) {
                sb.append(str[i]).append(" ");
            }
        }
        
        return sb.toString().trim();
    }
}

Followup:
Could you do it in-place without allocating extra space?

Analysis:
Use str.toCharArray() to change it to char array. Then reverse the whole array. Scan the array, if find a ‘ ‘, then reverse it from beginning. Update the start.

Time complexity : O(n)

Space complexity: O(1)

Code is below:

public class Solution {
    public void reverseWords(char[] s) {
        // O(n) O(1)
        
        if (s == null || s.length == 0) {
            return;
        }
        
        // reverse the whole array
        reverse(s, 0, s.length - 1);
        
        //reverse part of the words
        for (int i = 0, start = 0; i <= s.length; i++) {
            if (i == s.length || s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
    }
    
    public void reverse(char[] s, int start, int end) {
        while (start < end) {
            char c = s[start];
            s[start] = s[end];
            s[end] = c;
            start++;
            end--;
        }
    }
}

Leetcode 28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Analysis:

Brute force way. Go from the haystack and compare with needle, if it’s not the same, then break. Finally when j equals to the length of needle, we find the index.

Time complexity: O(mn)

Space complexity: O(1)

The code is below:

public class Solution {
    public int strStr(String haystack, String needle) {
        // O(mn)
        
        if (haystack == null || needle == null) {
            return -1;
        }
        
        int m = haystack.length();
        int n = needle.length();
        
        for (int i = 0; i < m - n + 1; i++) {
            int j = 0;
            for (j = 0; j < n; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
            
            if (j == n) {
                return i;
            }
        }
        
        return -1;
    }
}

Leetcode 12 & 13. Integer to Roman & Roman to Integer

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Analysis:

I(1)，V(5)，X(10)，L(50)，C(100)，D(500)，M(1000)

因为罗马数字都是由最大化的表示，比如10会表示成X而不是VV，所以我们可以从最大可能的表示向小的依次尝试。因为提示1-3999，所有的可能性不多，我们可以直接打表来帮助我们选择表示方法。在一个数量级中有四种可能的表示方法，以1-9为例，1-3是由I表示出来的，4是IV，5是V，6-8是V和若干个I，9是IX。

Time complexity: O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public String intToRoman(int num) {
        // O(n) O(n)
        
        if (num <= 0) {
            return "";
        }
        
        // List all possible cases
        String[] roman = new String[] {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] integer = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        
        StringBuilder sb = new StringBuilder();
        
        // Go through the integer list and find the largest base to add
        for (int i = 0; i < integer.length; i++) {             while (num >= integer[i]) {
                sb.append(roman[i]);
                num -= integer[i];
            }
        }
        
        return sb.toString();
    }
}

Followup:
Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Analysis:
Put the corresponding value in a map. Then go through the string from back, if last value is less than the previous value, then add the value. Otherwise, minus the value.

1. 相同的数字连写，所表示的数等于这些数字相加得到的数，例如：III = 3
2. 小的数字在大的数字右边，所表示的数等于这些数字相加得到的数，例如：VIII = 8
3. 小的数字，限于（I、X和C）在大的数字左边，所表示的数等于大数减去小数所得的数，例如：IV = 4

Time complexity: O(n)
Space complexity: O(n)

Below is the code:

public class Solution {
    public int romanToInt(String s) {
        // O(n) O(n)
        
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        Map<Character, Integer> map = new HashMap<Character, Integer>();
	    map.put('I', 1);
	    map.put('V', 5);
	    map.put('X', 10);
	    map.put('L', 50);
	    map.put('C', 100);
	    map.put('D', 500);
	    map.put('M', 1000);
	    
	    int len = s.length();
	    
	    int res = map.get(s.charAt(len - 1));
	    for (int i = len - 2; i >= 0; i--) {
	        if (map.get(s.charAt(i + 1)) <= map.get(s.charAt(i))) {
	            res += map.get(s.charAt(i));
	        } else {
	            res -= map.get(s.charAt(i));
	        }
	    }
	    
	    return res;
    }
}

Leetcode 8. String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

 

Requirements for atoi:The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Analysis:

Lots of corner case to be considered:

• number start or end with black space – use str.trim()
• number start with + / – – with a sign
• number out of range Integer range [-2147483648, 2147483647]

Note: to get the integer value of a string number, like ‘1’, we can use the char – ‘0’

For integer out of range, we need to check the res with the Integer.MAX_VALUE. If the last value is larger than 8 and the res = MAX /10, then it’s overflow.

To check a char is digit, we can use Character.isDigit(char).

Time complexity: O(n)

Space complexity: O(1)

Code is below:

public class Solution {
    public int myAtoi(String str) {
        // O(n) O(1)
        
        if (str == null || str.length() == 0) {
            return 0;
        }
        
        // To get rid of the leading and tailing blank space like " -1234 "
        str = str.trim();
        
        // Set the sign
        int sign = 1;
        
        int i = 0;
        
        // Check of "+" and "-"
        if (str.charAt(0) == '+') {
            i++;
        }
        
        if (str.charAt(0) == '-') {
            sign = -1;
            i++;
        }
        
        int res = 0;
        
        while (i < str.length() && Character.isDigit(str.charAt(i))) {             // Get the current digit             int digit = (int) (str.charAt(i) - '0');                          // Integer range [-2147483648, 2147483647]             if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && digit >= 8)) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            
            res = res * 10 + digit;
            i++;
        }
        
        return sign * res;
   
        //return Integer.valueOf(str);
    }
}

Leetcode 271 Encode and Decode Strings

Leetcode 271 Encode and Decode Strings

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Note:

• The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
• Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
• Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

Analysis:

To encode the string, we can add some symbols before it. For example, for string “abc”, we can add the length 3 before it. However, for string starting from numbers, like 123abc. This could result in 6123abc, which is not acceptable. Then we add an ‘#’ between the length and the string.  So 3#abc is the decoded string.

To decode the string, we can search the ‘#’ symbol. The number before it is the length for the string, and the string after it with length is the string we want to decode.

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List strs) {
        // encode with stringlength + "#" + str
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str.length()).append("#").append(str);
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List decode(String s) {
        List result = new LinkedList<>();
        
        // Corner case
        if (s == null || s.length() == 0) {
            return result;
        }
        
        int start = 0;
        int end = 0;
        
        while (end < s.length()) {
            if (s.charAt(end) == '#') {
                // find the length
                int length = Integer.valueOf(s.substring(start, end));
                // add the str
                result.add(s.substring(end + 1, end + 1 + length));
                // reset the start and the end
                start = end + 1 + length;
                end = start;
            }
            end++;
        }
       return result; 
    }
}

Leetcode 151/186 Reverse Words in a String II

Leetcode  151 Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

Analysis

The main point for this is to use split(reexp) method. Basically, it returns the array, containing each word in the string. Then we go from the last word of the array and append them together, to construct the new array.

Time complexity: O(n)

Space complexity: O(n)

We go through the whole string, so the running time is O(n). We create another stringbuilder with the space of O(n).

Note: the result we returned must eliminate the last space.

Below is the code:

public class Solution {
    /**
     * @param s : A string
     * @return : A string
     */
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        String[] array = s.split(" ");
        StringBuilder sb = new StringBuilder();
        
        for (int i = array.length - 1; i >= 0; i--) {
            if (!array[i].equals("")) {
               sb.append(array[i]).append(" ");  
            }
        }
        
        if (sb.length() == 0) {
            return "";
        } else {
            // remove the last blank space 
            // note: substring(start, end), end char is excluded!
            return sb.substring(0, sb.length() - 1);
        }
        
    }
}

Leetcode 186 Reverse Words in a String II

Could you do the problem above in-place without allocating extra space?

This time, we can not use extra space to solve this problem.

The basic idea is to reverse the whole string firstly, then reverse each word. Given s = “the sky is blue“, we reverse it to be “eulb si yks eht“. Then we reverse each word to get “blue is sky the“.

To reverse each word, it can be checked whether we encounter a black space, if it is, then it’s a word, we reverse it. Then go to the next word.

public class Solution {
    public void reverseWords(char[] s) {
        // Corner case
        if (s == null || s.length == 0) {
            return;
        }
        
        // Firstly reverse the whole string
        reverse(s, 0, s.length - 1);
        
        // Then reverse each word
        for (int start = 0, i = 0; i <= s.length; i++) {
            if (i == s.length || s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
    }
    
    // Reverse each char from start to end
    public static void reverse(char[] s, int start, int end) {
        for (; start < end; start++, end--) {
            char c = s[start];
            s[start] = s[end];
            s[end] = c;
        }
    }
}

Find the first non-repeating character in a String

Given a String, find the first non-repeating character.

For this problem, we can use hashmap to solve it. Two scans are needed for the whole process.

1. Go through the whole string, put the occurrence of each character in the hashmap. Key is each char, value is the number of occurrence.
2. Go through the hashmap, find the first key which has value of 1.

Time complexity: O(n)

public static Character firstNonRepeated (String str) {
	HashMap<Character, Integer>  hashmap = new HashMap<>();

	// put the occurrence of each char in the hashtable
	for (int i = 0; i < str.length(); i++) {
		char c = str.charAt(i);
		if (hashmap.containsKey(c)) {
			hashmap.put(c, hashmap.get(c) + 1);
		} else {
			hashmap.put(c, 1);
		}
	}

	// Search for the first non repeating char
	for (i = 0; i < str.length(); i++) {
		char c = str.charAt(i);
		if (hashmap.get(c) == 1) {
			return c;
		}
	}
	return null;
}

Lintcode String Permutation

Lintcode String Permutation

Given two strings, write a method to decide if one is a permutation of the other.

abcd is a permutation of bcad, but abbe is not a permutation of abe

Here permutation means one arrangement of the characters.

Analysis:

This problem is very similar to the one about valid anagrams. Basically an array to hold the number of occurrence of  each character. Then check whether the result to be zero in each cell of the array. If it’s, then yes, otherwise no.

public class Solution {
    /**
     * @param A a string
     * @param B a string
     * @return a boolean
     */
    public boolean stringPermutation(String A, String B) {
        // Create a table to hold the occurences of each char
        int[] counter = new int[200];
        
        for (int i = 0; i < A.length(); i++) {
            counter[A.charAt(i)]++;
        }
        
        for (int i = 0; i < B.length(); i++) {
            counter[B.charAt(i)]--;
        }
        
        for (int cnt: counter) {
            if (cnt != 0) {
                return false;
            }
        }
        
        return true;
    }
}

Leetcode 125 Valid Palindrome

Leetcode 125 Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

In Wiki, Palindrome(回文) means a word, phrase, number, or other sequence of characters which reads the same backward or forward. Allowances may be made for adjustments to capital letters, punctuation, and word dividers.

Analysis:

Basically, a palindrome can be checked by start from both the beginning and the end of the string, comparing them char by char. If they’re the same until all chars being checked, then it’s true. Otherwise, it’s false.

From the above thinking, it should remind us to use two pointers. Fundamentally, we can have two pointers pointing to the start and then end of the string. Move forward and backward at the same time. If they’re all the same, then it’s true, otherwise, its’ false.

Note:

• empty string is palindrome
• there exists chars other than characters and digit numbers
• change all chars to lowercase firstly

When facing specific characters, we just need to ignore them and continue move forward/backward.

Time complexity: O(n)

Space complexity: O(1)

Then comes the code:

public class Solution {
    public boolean isPalindrome(String s) {
        // Two pointers O(n)
        
        if (s == null || s.length() == 0) {
            return true;
        }
        
        s = s.toLowerCase();
        
        int start = 0;
        int end = s.length() - 1;
        
        while (start < end) {
            // Move forward
            if (!Character.isLetterOrDigit(s.charAt(start))) {
                start++;
                continue;
            }
            
            // Move backward
            if(!Character.isLetterOrDigit(s.charAt(end))) {
                end--;
                continue;
            }
            
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                return false;
            }
        }
        return true;
    }
}

In the code above we used the default method isLetterOrDigit(char c) to check whether a char is a letter or a digit. There’s also other method to check it.

public boolean isValidCharater(char c) {
    return (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
}

A easier to understand solution:

public class Solution {
    public boolean isPalindrome(String s) {
        // O(n) O(1)
        
        if (s == null || s.length() == 0) {
            return true;
        }
        
        int left = 0;
        int right = s.length() - 1;
        
        // Change all chars to lowercase
        String str = s.toLowerCase();
        
        while (left = 'a' && c = '0' && c <= '9');
    }
}