Java Solution with 1ms, Time Complexity O(mn)


  • 0
    M
    public String longestCommonPrefix(String[] strs) {
            // check existing
            if (strs == null || strs.length==0) {
                return "";
            }
            // search for the shortest string
            String shortest = strs[0];
            for (String str : strs) {
                if (str.length()<shortest.length()) {
                    shortest = str;
                }
            }
            boolean flag = true;
            while (!"".equals(shortest)) {
                for (String str : strs) {
                    flag = true;
                    // check if starting with the shortest string
                    // if not, remove the last char of the shortest
                    if (!str.startsWith(shortest)) {
                        shortest = shortest.substring(0, shortest.length()-1);
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    return shortest;
                }
            }
            return "";
    }

Log in to reply
 

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