String related questions

1. 
   Question:
   Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures.
   
   Answer: make assumption about the string is an ASCII string (if Unicode string, need more storage space).
   
   

   //use Java HashSet directly 
   public boolean isUniqueCharsWithHash(String str) {
      Set charSet = new HashSet();
      for (int i=0; i < str.length();i++) {
         if (charSet.contains(str.charAt(i))) {
   	return false;
         } else {
   	charSet.add(str.charAt(i));
         }
      }
      return true;
   }
   //use a size:256 boolean array to detect if the character exists or not
   public static boolean isUniqueChars(String str) {
     if (str.length() > 256) {
      return false;
     }
     boolean[] char_set = new boolean[256];
     for (int i = 0; i < str.length(); i++) {
      int val = str.charAt(i);
      if (char_set[val]) return false;
      char_set[val] = true;
     }
     return true;
    }
   
   //if string only contains a-z(or A-Z), only need 26 bits. 
   //An 4bytes integer has 32bits, each bit can act as a boolean flag
   
   public boolean isUniqueChars2(String str) {
       int checker = 0;
       String lowerCaseStr = str.toLowerCase();
       for(int i=0; i< lowerCaseStr.length(); i++) {
           int val = lowerCaseStr.charAt(i) - 'a';
           if((checker &(1<< val))>0) {
               return false;
           }
           checker |=(1<< val);
       }
       return true;
   }
   

2. 
   Question: reverse words in a string, E.X.: "who are you" ==> "you are who"; "who" ==>"who"
   Answer:
   strategy: reverse the whole string once, and then reverse each word so that it's in the right order
   remember how to convert String to CharArray and how to construct String from CharArray
   
   

   public static void reverseCharArr(char[] arr, int start, int end) {
           char tmp;
           while (start <= end) {
               tmp = arr[start];
               arr[start] = arr[end];
               arr[end] = tmp;
               start++;
               end--;
           }
       }
   
       public static String reverseWords2(String str) {
           if (str == null || str.isEmpty())
               return str;
           char[] strArr = str.toCharArray();
           reverseCharArr(strArr, 0, strArr.length - 1);
           int start = 0, end = 0; //two pointers for each word
           while (end < strArr.length) {
               if (strArr[end] != ' ') {
                   start = end;
                   // to address single world case 'who'->'ohw'->'who'
                   // need to check if end < strArr.length
                   while (end < strArr.length && strArr[end] != ' ') {
                       end++;
                   }
                   end--;
                   reverseCharArr(strArr, start, end);
               }
               end++;
           }
           return new String(strArr);
       }
   
       public static void main(String[] args) {
           String strArr[] = { "who are you", "", "  ", "who" };
           for (String str : strArr) {
               System.out.println("original string is:" + str);
               System.out.println("reversing words string is:"
                       + reverseWords2(str));
   
           }
       }
   

3. 
   Question: Implement atoi to convert a string to an integer.
   
   Answer:
   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. LeetCodeLink
   
   

   public class Solution {
           public int atoi(String str) {
               str = str.trim();// trim head and tail spaces
               int length = str.length();
               if (length == 0)
                   return 0;
               long num = 0;
               boolean neg = false;
   
               char firstChar = str.charAt(0);
               if (firstChar == '-') {
                   neg = true;
               } else if (firstChar == '+') {
   
               } else if (firstChar >= '0' && firstChar <= '9') {
                   num = firstChar - '0';
               } else {
                   return 0;
               }
   
               for (int i = 1; i < length; i++) {
                   // consider any other non-digit characters as illegal, and break
                   // immediately
                   if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                       num = num * 10 + (str.charAt(i) - '0');
                       if (num > Integer.MAX_VALUE && neg == false) {
                           return Integer.MAX_VALUE;
                       } else if (num > Integer.MAX_VALUE && neg == true) {
                           return Integer.MIN_VALUE;
                       }
                   } else {
                       break;
                   }
               }
               if (neg) {
                   num *= -1;
                   if (num < Integer.MIN_VALUE)
                       return Integer.MIN_VALUE;
               }
               return (int) num;
           }
       }
   

4. 
   Question: Longest Substring Without Repeating Characters QuestionLink Given a string, find the length of the longest substring without repeating characters.
   For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
   
   Answer:
   

   public class Solution {
       public int lengthOfLongestSubstring(String s) {
           //WRONG ANSWER: can't move directly over the not longest substring
           //Example: 'ddqscdxrjmowfrxs', the longest substring will be 'qscdxrjmowfrxs'
           /*
           if(s==null||s.isEmpty()) return 0;
           int length = s.length();
           Set subSet = new HashSet();
           int max=1;
           int start=0, end=0;
           for(int i=0; i < length; i++) {
               if(!subSet.contains(s.charAt(i))) {
                   end++;
                   subSet.add(s.charAt(i));
               } else {
                   end=i;
                   if(end-start > max) {
                       max=end-start;
                   }
                   start=i;
                   subSet.clear();
                   subSet.add(s.charAt(i));
               }
           }
           max=Math.max(max, end-start);
           return max;
           */
           // return Solution1(s);
           return Solution2(s);
           
          
       }
       
       //Worst case: O(n^2)  'abcdefg'
       public int Solution1(String s) {
            if (s == null || s.isEmpty())
               return 0;
           int length = s.length();
           Set subSet = new HashSet();
           int count = 1;
           for (int i = 0; i < length; i++) {
               for(int j=i; j < length; j++) {
                   if (!subSet.contains(s.charAt(j))) {
                       subSet.add(s.charAt(j));
                   } else {
                       count = Math.max(count, subSet.size());
                       subSet.clear();
                       break;
                       
                   }
                   if(j==length-1) {
                       count = Math.max(count, subSet.size());
                   }
               }
           }
           return count;
       }
       
       //refer to : http://leetcode.com/2011/05/longest-substring-without-repeating-characters.html
       //Worst case: 2n, O(n) solution
       //use two pointer[start, end] to segement the substring. 
       //The key is: when hitting a repeated character, it's safe to move start to the first different char as s[end].
       //For example: 'abcabc', s=0, e=3; next move s=1, e=4; 'abcdefgehkced': s=0, e=7; next move s=5, e=8
       public int Solution2(String s) {
           if (s == null || s.isEmpty())
               return 0;
           int length = s.length();
           Set subSet = new HashSet();
           int count = 1;
           int start=0, end=0;
           while(end < length) {
               if(subSet.contains(s.charAt(end))) {
                   count = Math.max(count, end-start);
                   while(s.charAt(start) != s.charAt(end)) {
                       subSet.remove(s.charAt(start));
                       start++;
                   }
                   start++;
                   end++;
               } else {
                   subSet.add(s.charAt(end));
                   end++;
               }
           }
           count = Math.max(count, length-start); //remember to update count after the main loop
           return count;
       }
   }
   

5. 
   Question: Given two numbers represented as strings, return multiplication of the numbers as a string. QuestionLink
   For example, "0"*"0"=="0", "11"*"11"="121", "12"*"4567"="54804"
   
   Answer:
   

   public String multiply(String num1, String num2) {
           
           int len1 = num1.length();
           int len2 = num2.length();
           
           int len3 = len1+len2;  
           int[] num3 = new int[len3]; //multi can't be longer than len3
           
           for (int i=len1-1;i>=0;i--) {
               int carry = 0, j, t;
               for (j=len2-1;j>=0;j--) {
                   t = carry + num3[i+j+1] + (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
                   num3[i+j+1] = t%10;
                   carry = t/10;
               }
               num3[i+j+1] = carry; //j will be -1 after inner loop, keep 
           }
           
           StringBuilder sb = new StringBuilder();
           int i=0;
           while (i < len3-1 && num3[i] == 0) i++; //if no carryOver, skip those coefficients
           while(i < len3) {
               sb.append(num3[i]);
               i++;
           }
           return sb.toString();
       }
   

6. 
   Question: Given an absolute path for a file (Unix-style), simplify it. QuestionLink
   For example,
   
   path = "/home/", => "/home"
   
   path = "/a/./b/../../c/", => "/c"
   
   
   
   Answer: input like '/...' will return '/'
   

   public static String simplifyPath(String path) {
           int len = path.length();
           if (len <= 1)
               return path;
           ArrayDeque result = new ArrayDeque();
           for (int i = 0; i < len; i++) {
               char c = path.charAt(i);
               if (c == '/') {
                   if (result.size() == 0 || result.getLast() != '/') {
                       result.add(c);
                   }
               } else if (c == '.') {
                   if (i + 1 < len && path.charAt(i + 1) == '.') {
                       i++; // move to 2nd '.'
                       result.pollLast(); // pop last previous '/'
   
                       // pop previous directory name until hitting its '/'
                       while (result.size() > 0 && result.peekLast() != '/') {
                           result.pollLast();
                       }
                   }
               } else {
                   result.add(c);
               }
           }
   
           // to address corner case: "/../" or "/..", to return '/'
           if (result.size() < 2)
               return "/";
   
           // remove tailing '/'
           if (result.peekLast() == '/')
               result.pollLast();
   
           StringBuilder sb = new StringBuilder();
           for (Iterator iter = result.iterator(); iter.hasNext();) {
               sb.append(iter.next());
           }
           return sb.toString();
       }
   

7. 
   Question: Given a string containing only digits, restore it by returning all possible valid IP address combinations.
   
   For example:
   Given "25525511135",
   
   return ["255.255.11.135", "255.255.111.35"]. (Order does not matter) QuestionLink
   
   
   Answer:
   

   public class Solution {
   	public ArrayList <string> restoreIpAddresses(String s) {
   		ArrayList <string> res = new ArrayList <string>();
   		if (s.length() > 12) return res;
   		dfs(res, "", s, 0);
   		return res;
   	}
   
   	public void dfs(ArrayList <string> res, String buff, String s, int count) {
   		if (count == 3 && isValid(s)) { // if s is a valid 4th substring, add it to result and return
   			res.add(buff + s);
   			return;
   		}
   
   		for (int i = 1; i < 4 && i < s.length(); i++) { // make sure also check i < s.length()
   			String substr = s.substring(0, i);
   			if (isValid(substr))
   				dfs(res, buff + substr + ".", s.substring(i), count + 1);
   		}
   	}
   
   	public boolean isValid(String s) {
   		if (s.charAt(0) == '0')
   			return s.equals("0");
   		int num = Integer.parseInt(s);
   		return num >= 0 && num <= 255;
   	}
   }
   

8. 
   Question: TEMPLATE QuestionLink
   
   
   Answer: