O(n) space complexity and O(n*m) time complexity. Using character array as HashMap.


  • 0
    O

    O(n) space complexity
    O(n*m) time complexity
    n - length of the word in array
    m - array size

    How do you think sorting array will be faster or no?

    public class Solution {
        public String longestCommonPrefix(String[] strs) {
            if (strs.length == 0) {
                return "";
            }
            String current = strs[0];
            int i, j, end = current.length();
            int size = end;
            char[] prefix = new char[size];
            for(i = 0; i < size; i++) {
                prefix[i] = current.charAt(i);
            }
            for(i = 1; i < strs.length; i++) {
                current = strs[i];
                size = current.length();
                if (size == 0) {
                    return "";
                }
                for(j = 0; j < size && j < end; j++) {
                    if (size < end) {
                        end = size;
                    }
                    if (prefix[j] != current.charAt(j)) {
                        end = j;
                    }
                }
            }
            current = "";
            for(i = 0; i < end; i++) {
                current += prefix[i];
            }
            
            return current;
        }
    }
    

Log in to reply
 

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