[LeetCode]Longest Common Prefix

Longest Common Prefix

在一陣列中，找出所有字串共同的字首且長度最長的字首，如果沒有匹配的結果回傳空值。

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.

解法

先找出陣列中最短的字串，並利用該字串一一去比對，只要符合是共同字首且長度最長的字首變停止比對，反之回傳空值。

class Solution
{
    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs)
    {
        // 找出陣列中長度最小的字串
        $min_len = strlen($strs[0]);
        $now_len = strlen($strs[0]);
        $min_len_str = $strs[0];
        foreach ($strs as $i => $str) {
            $now_len = strlen($str);

            if ($min_len > $now_len) {
                $min_len = $now_len;
                $min_len_str = $str;
            }
        }

        // 一一比對陣列中的字串
        for ($i = $min_len; $i > 0; $i--) {
            $count = 0;
            foreach ($strs as $str) {
                // strpos = 0，表示找到第 0 位置上的(第一個)字元
                if (
                    strpos($str, substr($min_len_str, 0, $i)) !== false
                    && strpos($str, substr($min_len_str, 0, $i)) == 0
                ) {
                    $count++;
                }

                // 所有字串皆符合條件
                if ($count == count($strs))
                    return substr($min_len_str, 0, $i);
            }
        }

        return '';
    }
}

參考：PHP - strpos