Longest Common Prefix

Longest Common Prefix

Given k strings, find the longest common prefix (LCP).

Example

For strings "ABCD", "ABEF" and "ACEF", the LCP is "A"

For strings "ABCDEFG", "ABCEFG" and "ABCEFA", the LCP is "ABC"

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    String lcp = strs[0];
    for (int i = 1; i < strs.length; i++) {
        lcp = getLCP(lcp, strs[i]);
    }
    return lcp;
}

public String getLCP(String s1, String s2) {
    StringBuilder sb = new StringBuilder();
    int n = Math.min(s1.length(), s2. length());
    for (int i = 0; i < n; i++) {
        if (s1.charAt(i) == s2.charAt(i)) {
            sb.append(s1.charAt(i));
        } else {
            break;
        }
    }
    return sb.toString();
}

 

FacebookTwitterGoogle+Share

Palindrome Partitioning

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution: DFS, Subsets变种题 考虑每个间隙是partition还是不partition

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    partitionHelper(s, new ArrayList<String>(), result);
    return result;
}

public void partitionHelper(String s, ArrayList<String> curr, List<List<String>> result) {
    if (s.length() == 0) {
        result.add(new ArrayList<String>(curr));
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        String currString = s.substring(0, i + 1);
        if (isPalindrome(currString)) {
            curr.add(currString);
            partitionHelper(s.substring(i + 1), curr, result);
            curr.remove(curr.size() - 1); //important
        }
    }
}

public boolean isPalindrome(String s) {
    int start = 0;
    int end = s.length() - 1;
    while (start <= end) {
        if (s.charAt(start) != s.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

Leetcode: Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

 

public boolean isNumber(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s==null||s.length()==0){
            return false;
        }
        //continuous zeros from beginning since begin is true
        int cont = 0;
        boolean hasDot = false;
        boolean begin = false;
        boolean end = false;
        boolean hasSign = false;
        boolean hasE = false;
        
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            
            
            if(c=='+'||c=='-'){
                if(hasSign||begin){
                    return false;
                }else{
                    hasSign = true;
                }
                continue;
            }
            
            if(c=='e'){
                if(hasE||!begin){
                    return false;
                }else{
                    return isInteger(s.substring(i+1));
                    //return true;
                }
            }
            
            if(c=='.'){
                if(hasDot||end){
                    return false;
                }else{
                    hasDot = true;
                }
                continue;
            }
            
            if(c==' '){
                if((begin ||hasSign) && !end){
                    end=true;
                }
                continue;
            }
            
            if(!(isDigit(s,i))){
                return false;
            }else{
                if(end){
                    return false;
                }else{
                    if(!begin){
                        begin=true;
                    }
                }
            }
            
            
        }
        
        if(!begin){
            return false;
        }
        return true;
        
        
    }
    public boolean isInteger(String s){
        if(s==null||s.length()==0){
            return false;
        }
        if(s.length()==1 && isDigit(s,0)){
            return true;
        }
        char c = s.charAt(0);
        if(c=='0'){
            return ifAllSpace(s.substring(1));
        }
        int zeors = 0;
        for(int i=0;i<s.length();i++){
            if(i==0){
                if(c=='+'||c=='-'){
                    return isIntegerWithoutSign(s.substring(i+1));
                }else
                if(!isDigit(s,i)){
                    return false;
                }
            }else
            if(!isDigit(s,i)){
                if(c==' '){
                    return ifAllSpace(s.substring(i+1));
                }else{
                    return false;
                }
            }
        }
        return true;
    }
    
    public boolean ifAllSpace(String s){
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)!=' '){
                return false;
            }
        }
        return true;
    }
    
    public boolean isIntegerWithoutSign(String s){
        if(s==null||s.length()==0){
            return false;
        }
        if(s.length()==1 && isDigit(s,0)){
            return true;
        }
        char c = s.charAt(0);
        if(c=='0'){
            return false;
        }
        for(int i=0;i<s.length();i++){
            if(!isDigit(s,i)){
                if(c==' '){
                    return ifAllSpace(s.substring(i));
                }else{
                    return false;
                }
            }
        }
        return true;
    }
    
    public boolean isDigit(String s,int index){
        char c = s.charAt(index);
        if(c<(int)'0' || c>(int)'9'){
            return false;
        }
        return true;
    }

Leetcode: Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

public String strStr(String haystack, String needle) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(needle==null){
            return haystack;
        }

        int start = 0;
        int index1 = 0;
        int index2 = 0; 
        while(index1<haystack.length() && index2<needle.length()){
            if(haystack.charAt(index1)==needle.charAt(index2)){
                index1++;
                index2++;                
            }else{
                start++;
                index1=start;
                index2=0;

            }
        }
        if(index2==needle.length() && index1-start==needle.length()){
            return haystack.substring(start);
        }else{
            return null;
        }
    }