Leetcode: Longest Common Prefix

This question is asked quite often at Amazon and other companies. 

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". 

Example 1:

Input: strs = ["flower","flow","flight"]

Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]

Output: ""

Explanation: There is no common prefix among the input strings. The  thing where it gets complex is when we have different strings. We need to make sure that we don't go out of bounds and the longest common prefix, as a result, is limited by the shortest word. The longest common prefix is defined by the length of the shortest word. So we first define string, and just going to start as an empty string, because we haven't checked characters. It's always good to have error checking, We go through all the characters in the first word arbitrarily, and go through all the characters in the first string, and see if every other character has this, and go through all the strings, and add the character if is, if not, then return it, If the 2 characters are not the same return it.

So we'll have an index to represent to characters. Then, for every character, now we need to go through all the strings, to make sure they have the same character in the index position. We don't want to compare a current string's character with its own character, and we keep comparing and have multiple conditions. Then we see if the index is greater than or equal to a string or if does not equat to the character at index, return the longest common prefix, because we have gotten out of bounds in one of the string. Then we can append that character c to our longest common prefix, and go over all of the indices. We have gone through all the characters in the first string, and compare them all of the other characters in the other string, and then we actually have longest common prefix.

class Solution {

    public String longestCommonPrefix(String[] strs) {

        String longestCommonPrefix = "";

        //check if the string is empty

        if(strs == null || strs.length == 0) return longestCommonPrefix;

        int index = 0;

        //go in the first string and check

        for(char c: strs[0].toCharArray()) {

            //for all the strings, check if each character matches

            for(int i = 1; i < strs.length; i++) {

                if(index >= strs[i].length() || c != strs[i].charAt(index)) {

                    return longestCommonPrefix;

                }

            }

        //increment the charater of the first string, and the index to see if you 

        //reached the end of the string, since the you found the prefix.

        longestCommonPrefix += c;

        index++;

        }

        //return the prefix.

         return longestCommonPrefix;

    }

}