14. Longest Common Prefix

/*
Write a function to find the longest common prefix string amongst an array of strings.
思想：拿第一个 str 作为标准，后面的字符串依次做比对。
复杂度：时间复杂度 O(nm), 空间复杂度 O(m), m 是第一个字符串的长度。
这题的关键在于，不断缩减比对的长度，例如下一个比对的长度小于当前，则最小长度就变成了下一个的长度，
如果同下一个比对的过程中出现不匹配，则最小长度又变成了不匹配长度位置的上一位。
*/

import Foundation

func longestCommonPrefix(_ strs: [String]) -> String {
    guard strs.count > 0 else {
        return ""
    }

    var compareArray = [Character](strs[0].characters)

    for s in strs {
        let currentArray = [Character](s.characters)

        //因为始终共有长度是最小长度，所以每次都用最小长度去作为下一次比较的基础
        if compareArray.count > currentArray.count {
            compareArray = Array(compareArray[0 ..< currentArray.count])
        }

        for i in 0..<compareArray.count {
            if currentArray[i] != compareArray[i] {
                compareArray = Array(compareArray[0 ..< i])
                break
            }
        }
    }
    return  String(compareArray)

}

print(longestCommonPrefix(["abc", "ab", "ab", "abc"]))