You are given an array of strings strs. A prefix is the first few letters of a string. Find the longest prefix that all the strings share.
Return that prefix. If the strings have no common prefix, return an empty string "".
Examples
Example 1:
Input: strs = ["interview","internet","internal"]
Output: "inter"
Explanation: All three start with "inter".
Example 2:
Input: strs = ["moon","sun"]
Output: ""
Explanation: The first letters are different.
Example 3:
Input: strs = ["same"]
Output: "same"
Explanation: With one string, the whole string is the answer.