Longest Common Prefix

Given an array of strings strs, return the longest common prefix string amongst all strings in the array using a trie (prefix tree).

If there is no common prefix, return an empty string "".

Examples

Example 1:

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

Output: "fl"

Explanation: The longest common prefix shared by all three strings is "fl".

Example 2:

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

Output: ""

Explanation: There is no common prefix among the input strings.

Example 3:

Input: strs = ["interspecies","interstellar","interstate"]

Output: "inters"

Explanation: All three strings share the prefix "inters".

Constraints

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.