strStr KMP solution Java

KMP :
prefix array to find prefix and suffix.
use for - while loop .

class Solution {
    /**
     * Returns a index to the first occurrence of target in source,
     * or -1  if target is not part of source.
     * @param source string to be scanned.
     * @param target string containing the sequence of characters to match.
     */
    public int strStr(String source, String target) {
        if(source==null || target==null)
            return -1;
        if(target.length()==0)
            return 0;
        int[] prefix= new int[target.length()];
        int k=0;
        for(int i=1;i<target.length();i++){
            while(k>1 && target.charAt(k)!= target.charAt(i))
                k=prefix[k-1];
            if(target.charAt(i)==target.charAt(k))
                k++;
            prefix[i]=k;
        }
        k=0;
        for(int i=0;i<source.length();i++){
             while( k>1 && source.charAt(i)!= target.charAt(k))
                k=prefix[k-1];
            if(target.charAt(k) ==source.charAt(i))
                k++;
            if(k== target.length())
                return i-k+1;
        }
        return -1;
    }
}

lintcode @54 String to Integer(atoi) Java

1. trim string.
2. loop until . other character.
    judge if bigger than Integer.MAX_VALUE or smaller than Integer.MIN_VALUE

public class Solution {
    /**
     * @param str: A string
     * @return An integer
     */
    public int atoi(String str) {
        if(str==null)
            return 0;
        str=str.trim();
        int i=0;
        boolean neg=false;
        if(str.length()==0)
            return 0;
        if(str.charAt(0)=='-')
        {
            neg=true;
            i++;
        }else if(str.charAt(0)=='+')
            i++;
        int res=0;
        while(i<str.length()){
            char c= str.charAt(i);
            if(c=='.'){
                if(i-1<0 || str.charAt(i-1)>'9'|| str.charAt(i-1)<'0')
                    return 0;
                break;
            }else if( c>'9'|| c<'0')
                break;
            if(!neg && res>(Integer.MAX_VALUE -  c-'0')/10)
                return Integer.MAX_VALUE;
            else if(neg && res > (Integer.MIN_VALUE +  c-'0')/10 *-1 )
                return Integer.MIN_VALUE;
            else{
                res= res*10+ c-'0';
            }
            i++;
        }
        return neg? -res:res;
    }
}

lintcode@ 171 Anagrams Java

use isanagram method, same algorithm test if two strings are anagrams, then check whole string list.

public class Solution {
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    public List<String> anagrams(String[] strs) {
        List<String> res= new ArrayList<>();
        if(strs==null)
            return res;
        boolean flag= false;
        HashSet<Integer> tested= new HashSet<>();
        for(int i=0;i<strs.length;i++){
            flag=false;
            for(int j=i+1;j<strs.length;j++){
                if(tested.contains(i))
                    break;
                if(isanagram (strs[i], strs[j]))
                   {
                    res.add(strs[j]);
                    flag=true;
                    tested.add(j);
                   }
                }
            // added anagrams into the return
            if(flag){
                res.add(strs[i]);
            }
        }
        return res;
    }
   
    private boolean isanagram(String s1, String s2){
        if(s1==null || s2== null || s1.length()!=s2.length())
            return false;
        int[] mp= new int[256];
        for(int i=0;i<s1.length();i++){
            mp[s1.charAt(i)]++;
            mp[s2.charAt(i)]--;
        }
        for(int i=0;i<256;i++)
            if(mp[i]!=0)
                return false;
        return true;
    }
}