Count and Say, Integer to English Words, Length of Last Word, Simplify Path, Compare Version Numbers

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …
1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.

Solution

public static String countAndSay(int n) {
     if(n==0) return null;
     if(n==1) return "1";
 	String s="1";
     String news="1";
     for(int i=2;i<=n;i++){
         news="";
         for(int j=0;j<s.length();j++){
             int count=1;
             while(j+1<s.length() && s.charAt(j)==s.charAt(j+1)){
                  count++;
                  j++;
             }
             news+=String.valueOf(count)+s.charAt(j);
         }
         s=news;
     }
     return s;
 }

---

Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
For example,
123 -> “One Hundred Twenty Three”
12345 -> “Twelve Thousand Three Hundred Forty Five”
1234567 -> “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”

Solution

• Group by three digits, process from last digit, three and a time

static String[] twodigits = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", 		"Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
static String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
static String[] thousands = {"", "Thousand", "Million", "Billion"};

public static String numberToWords(int num) {
	if(num==0) return "Zero";
	String result="";
	int i=0;
	while(num>0){
		if(num%1000>0){
			result = helper(num%1000) + thousands[i] + " " + result;
		}
		num/=1000;
		i++;
	}
	return result.trim();
}
private static String helper(int num){
	if(num==0) return ""; //edge case
	if(num<20){
		return twodigits[num] + " ";//1-19
	}
	if(num<100){
		return tens[num/10] + " " + helper(num%10);//21-99
	}
	else{
		return twodigits[num/100] + " Hundred " + helper(num%100);//100-999
	}
}

---

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = “Hello World”,
return 5.

Solution

eh?

public static int lengthOfLastWord(String s) {
    s=s.trim();
    int i=s.length()-1;
    int len=0;
    while(i>=0 && s.charAt(i)>='A' && s.charAt(i)<='z'){
        i--;
    	len++;
    }
    return len;
}

---

Simplify Path

Given an absolute path for a file (Unix-style), simplify it.
For example,
path = “/home/“, => “/home”
path = “/a/./b/../../c/“, => “/c”

Solution

• Corner case 1
• Corner case 2

public static String simplifyPath(String path) {
       String[] s=path.split("/");
       Stack<String> stk = new Stack<String>();
       for(int i=0;i<s.length;i++){
           if(s[i].equals("..") && !stk.isEmpty()) stk.pop();
           else if(!s[i].equals("") && !s[i].equals(".") && !s[i].equals("..")) stk.push(s[i]);
       }
       String res="";
       if(stk.isEmpty()) return "/";
       while(!stk.isEmpty()){
       	res = "/" + stk.pop() + res;
       }
       return res;
   }

---

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

Solution

• To split a string with a literal ‘.’ character in Java, you must use split(“\\.”).

public static int compareVersion(String version1, String version2) {
     String[] s1 = version1.split("\\.");
     String[] s2 = version2.split("\\.");
     int len = Math.min(s1.length, s2.length);
     for(int i=0;i<len;i++){
         if(Integer.valueOf(s1[i]) < Integer.valueOf(s2[i])){
             return -1;
         }
         else if(Integer.valueOf(s1[i]) > Integer.valueOf(s2[i])){
             return 1;
         }
     }
     if(s1.length>s2.length){
     	int i=len;
     	while(i<s1.length){
     		if(Integer.valueOf(s1[i])==0)
     			i++;
     		else return 1;
     	}
     };
     if(s1.length<s2.length){
     	int i=len;
     	while(i<s2.length){
     		if(Integer.valueOf(s2[i])==0)
     			i++;
     		else return -1;
     	}
     };
     
     return 0;
 }