# 14. Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/
## Description
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 "".

**本節會使用之方法：**
1. Binary Tree：for 迴圈搭配 if 條件式
2. 字串轉陣列：list('string')
3. 取得陣列最小值（指定方法）：min(list,key=len)
4. 陣列轉字串："".join(list)
（""為指定符號（空白）、join 方法可以將 list 使用指定符號分隔）

## Example
Example 1:

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

Output: "fl"

Example 2:

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

Output: ""

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

Example 3:

Input: ["ca","a"]

Output: ""

## Solution

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
    
        # 空陣列直接回傳答案為 ""
        if strs == []:
            return ""
            
        # 陣列長度為 1 可直接回傳值為答案
        elif len(strs) == 1:
            return strs[0]
            
        # 陣列長度為 2 以上需要比較找出重複值
        else:
        
            # 取最小值與其餘值比較
            min_str = min(strs, key=len)
            min_list = list(min_str)
            strs.remove(min_str)
            
            # 其餘值重複比較（迴圈）
            for string in strs:        
                str_list = list(string)
                
                # 比較過程中需要的三個變數
                common = []
                sucess = 0
                previous = ""
                
                # 取得最小值中的每一個字符並開始檢查
                for data in min_list:
                
                    # 初次配對成功
                    if data in str_list and str_list.index(data) == 0:
                        common.append(data)
                        previous = str_list.index(data) 
                        str_list[str_list.index(data)] = ""
                        sucess = sucess + 1
                        
                    # 連續配對成功
                    elif data in str_list and str_list.index(data) == sucess:
                        sucess = sucess + 1
                        common.append(data)
                        previous = str_list.index(data)
                        str_list[str_list.index(data)] =""
                        
                    # 配對失敗
                    else:
                        break
                        
                # 比對後的結果取代最小值，再與剩餘字串比對
                min_list = common
                
            # 比對完成，回傳最終答案（需從 list 轉換成 string）
            return "".join(min_list)