Java code, no indexof() used, lower level implementation


  • 0
    D

    Before I see the discussion, I don't know actually we can use indexof() to simplify the code~~, My solution is longer but I want to share it with you.

    My idea is first find the min length among the Strings, set variable "prefixLen" to 1, then increase "prefixLen" exponentially or linearly in different situations.

    public class Solution {
        public String longestCommonPrefix(String[] strs) 
        {
            // special cases
            if (strs.length == 0) return "";
            if (strs.length == 1) return strs[0];
            
            // find min length among Strings
            int minLen = strs[0].length();
            for (String s : strs)
            {
                if (s.length() < minLen) minLen = s.length();
            }
            if (minLen == 0) return "";
            
            // pick the first char in first string
            String ts = strs[0].substring(0, 1);
            
            // initial prefix length
            int prefixLen = 1;
            
            // threshold for delta way, false means prefixLen will increase exponentially, true
            // means increase prefixLen linearly
            boolean threshold = false;
            
            while (prefixLen <= minLen)
            {
                int i = 1;
                
                for (; i < strs.length; i++)
                {
                    if (!ts.equals(strs[i].substring(0, prefixLen))) break;
                }
                // if i == strs.length, means we can safely increase prefixLen
                if (i == strs.length) 
                {
                    // increase prefixLen linearly
                    if (threshold == true) prefixLen = prefixLen + 1;
                    // already reach boundary
                    else if (prefixLen == minLen) break;
                    // increase prefixLen exponentially
                    else prefixLen = prefixLen * 2 > minLen? minLen : prefixLen * 2;
                }
                // this means we should shrink prefixLen
                else
                {
                    // set the threshold to true
                    if (threshold == false) threshold = true;
                    // if threshold is ture, means we cannot go further
                    else { prefixLen--; break; }
                    
                    // shrink prefixLen by half
                    prefixLen /= 2;
                    if (prefixLen == 0) break;
                    
                    // increase prefixLen by 1 after shrink it
                    prefixLen = prefixLen + 1;
                }
                
                // update ts, used to compare with other substrings
                ts = strs[0].substring(0, prefixLen);
            }
            
            // return longest prefix
            return strs[0].substring(0, prefixLen);
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.