Common String in Lists

Given a List of List of String, find the common String in all Lists, output them in sorted order. (could contain duplicates)

Naive Way:Need to consider case [[a,a,a],[a,a],[a,a,b]] outputs [a,a]. Use a HashMap as pattern, go through the lists, for each list, match it with the pattern, update the pattern, what left in the pattern is common string.

 public List<String> commonString(List<List<String>> lists){  
           List<String> rslt = new ArrayList<String>();  
           // edge case  
           if(lists.size()==0) return rslt;  
           // initialize pattern   
           Map<String, Integer> pattern = new HashMap<String, Integer>();  
           List<String> temp = lists.get(0);  
           setMap(pattern, temp);  
           // match pattern with other lists  
           for(int i = 1;i < lists.size();i++){  
                Map<String, Integer> map = new HashMap<String, Integer>();  
                setMap(map, lists.get(i));  
                Iterator it = pattern.entrySet().iterator();  
                List<String> toBeRemove = new ArrayList<String>();  
                while(it.hasNext()){  
                     Map.Entry pair = (Map.Entry)it.next();  
                     if(map.containsKey(pair.getKey()))  
                          pattern.put((String)pair.getKey(), Math.min(map.get(pair.getKey()),(int)pair.getValue()));  
                     else  
                          toBeRemove.add((String)pair.getKey());  
                }  
                for(int j = 0;j < toBeRemove.size();j++)  
                     pattern.remove(toBeRemove.get(j));  
           }  
           // collect results  
           Iterator it = pattern.entrySet().iterator();  
           while(it.hasNext()){  
                Map.Entry pair = (Map.Entry)it.next();  
                for(int i = 0;i < (int)pair.getValue();i++)  
                     rslt.add((String)pair.getKey());  
           }  
           // sort the result  
           Collections.sort(rslt);  
           return rslt;  
      }  
      private void setMap(Map<String, Integer> map, List<String> list){  
           for(int i = 0;i < list.size();i++){  
                if(!map.containsKey(list.get(i)))  
                     map.put(list.get(i), 1);  
                else  
                     map.put(list.get(i), map.get(list.get(i))+1);  
           }  
      }  

Finding all palindromes in String

Finding all palindromes in String.

Naive Thinking: Use the method described in  longest-palindromic-substring . There are covered ranges for each character. That's the result we want.

Time complexity O(n^2) (because to generate output, Hoops, that seems not great benefit using longest-palindrome's algorithm) 
Space O(n^2) (Also because of the output).

 import java.util.List;  
 import java.util.ArrayList;  
 import java.util.Set;  
 import java.util.HashSet;  
 public class Solution{  
   public static void main(String args[]){  
     Solution s = new Solution();  
     List<String> list = s.findAllPalindrome("abbbbabaaabab");  
     System.out.println(list);  
   }  
   public List<String> findAllPalindrome(String s){  
     List<String> list = new ArrayList<String>();  
     Set<String> set = new HashSet<String>();  
     String str = preProcess(s);  
     int f[] = new int[str.length()]; // coverage  
     int p = 0; // pivot  
     for(int i = 1;i < str.length();i++){  
       // check if position i is in pivot's coverage  
       if(p + f[p] > i){  
         if(2*p-i - f[2*p-i] > p-f[p])  
           f[i] = f[2*p-i];  
         else  
           f[i] = f[p] - (i-p);  
       }else{  
         f[i] = 0;  
       }  
       // extend if necessary  
       int j = 1;  
       while(i-f[i]-j >= 0 && i+f[i]+j < str.length() && str.charAt(i+f[i]+j)==str.charAt(i-f[i]-j)) j++;  
       f[i] += j-1;  
       // check if need to replace pivot  
       if(i+f[i] > p+f[p]) p = i;  
     }  
     // generate result  
     for(int i = 0;i < f.length;i++)  
       for(int j = 2;j <= f[i];j++)  
         set.add(s.substring((i-j)/2,(i+j+1)/2));  
     list.addAll(set);  
     return list;  
   }  
   private String preProcess(String s){  
     StringBuilder str = new StringBuilder();  
     for(int i = 0;i < s.length();i++){  
       str.append("#");  
       str.append(s.charAt(i));  
     }  
     str.append("#");  
     return str.toString();  
   }  
 }  

Arithmetic Slice

From http://codesays.com/2014/solution-to-count-arithmetic-sequence/
There is another question related to Arithmetic Sequence Longest Arithmetic Sequenece

Arithmetic Slice, is a slice of an array num[i..j] with at least size 3 and has num[i], num[i+1]...num[j-1],num[j] forming an arithmetic sequence.

For example:

Input:

[-1, 1, 3, 3, 3, 2, 1, 0]

Output:

5

Explanation:

There are five arithmetic sequences in the input:

[-1, 1, 3], [3, 3, 3], [3, 2, 1], [2, 1, 0], and [3, 2, 1, 0]

O(n) time complexity is required. Once the number of Arithmetic Slice is greater than 1000000000, return -1.

Naive Thinking:这道题一开始的例子给的好烦人，最好自己写一两个例子。
[1 2 3] has 1 arithmetic slice
[1 2 3 4] has 3 arithmetic slice since [1 2 3], [2 3 4] and [1 2 3 4].

 这样就很清楚了，如果再来个[1 2 3 4 5]， 那就有6个了，就是连续的差等数列会使得count 要算上每一个子集。遍历的时候追溯直到不能形成等差数列为止。

 算法复杂度是O(n)， space O(1)。

 public static final int limit = 1000000000;  
   public int getLAS(int[] A){  
     int count = 0;  
     // edge case  
     if(A.length <= 2) return count;  
     // main process  
     int i = 1;  
     while(i+1 < A.length){  
       int k = i+1;  
       // if its neighbor and itself form an AS, count++  
       if(2*A[i] == A[i-1]+A[k]){  
         count++;  
         if(count > limit) return -1;  
         // if two neighbors match, go through all the way until not match  
         while(k+1 < A.length && 2*A[k] == A[k-1]+A[k+1]){  
           k++;  
           count += (k-i);  
           if(count > limit) return -1;  
         }  
       }  
       // increment  
       i = k;  
     }  
     return count;  
   }