Viiisit [LeetCode] - 14. Longest Common Prefix

keep learning, keep coding!

Problem - Longest Common Prefix

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 “”.

翻譯蒟蒻

在給定的陣列中找出最常出現的前綴字，如果沒有的話，就回傳空字串 ""。

• 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.

---

Solution - JavaScript

Solution 1:

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
  if (strs.length === 0) {
    return "";
  }

  for (let i = 0; i < strs[0].length; i++) {
    let char = strs[0][i];

    // 比較該字母在其他字串相同位置的字母
    for (let j = 1; j < strs.length; j++) {
      if (i >= strs[j].length || char !== strs[j][i]) {
        return strs[0].substring(0, i);
      }
    }
  }

  return strs[0];
};

Solution 2:

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
  if (strs.length === 0) {
    return "";
  }

  // 將陣列排序，這樣具有相同前綴的字串就會被排在一起
  strs.sort();

  // 比較排序後的陣列的第一個字串和最後一個字串的每個字母
  let firstString = strs[0];
  let lastString = strs[strs.length - 1];
  let i = 0;

  // 如果找到不同的字母或某個字串的長度不足，就返回目前的前綴
  while (i < firstString.length && firstString[i] === lastString[i]) {
    i++;
  }

  return firstString.substring(0, i);
};

Solution - Ruby

def longest_common_prefix(strs)
  return "" if strs.empty?

  # 先排序，並更新 strs 陣列
  strs.sort!

  # 比較排序後的陣列的第一個字串和最後一個字串的每個字符
  first_string, last_string = strs.first, strs.last
  i = 0

  while i < first_string.length && first_string[i] == last_string[i]
    i += 1
  end

  first_string[0, i]
end

Solution - PHP

function longestCommonPrefix($strs) {
    if (empty($strs)) {
        return "";
    }

    sort($strs);

    $firstString = $strs[0];
    $lastString = end($strs);
    $i = 0;

    while ($i < strlen($firstString) && $firstString[$i] == $lastString[$i]) {
        $i++;
    }

    return substr($firstString, 0, $i);
}

$strs1 = ["flower", "flow", "flight"];
$strs2 = ["dog", "racecar", "car"];

echo longestCommonPrefix($strs1);  //  "fl"
echo longestCommonPrefix($strs2);  //  ""

PHP 方法筆記

• empty 是一個用來檢查變數是否為空或未設定的函數。
  具體而言，empty 函數會檢查一個變數是否為以下情況之一：

  1. 變數未被設定（未被賦值）。
  2. 變數的值為空字串 ""。
  3. 變數的值為 0（作為整數）。
  4. 變數的值為 "0"（作為字串）。
  5. 變數的值為 null。
  6. 變數的值為 false。
  7. 變數的值為空陣列 array()。
  8. 變數不存在。

  如果變數符合上述任何一種情況，empty 函數將返回 true，否則返回 false。

---

• sort 用來對陣列（array）進行排序的方法。

  sort 會直接修改原始陣列，並返回排序後的結果。如果是要保留原始陣列的副本而對副本進行排序，可以使用 array_copy 函數。

---

• end 用於獲取陣列中最後一個元素的函數。

  函數的基本語法如下：

  $lastString = end($strs);

---

• substr 是 PHP 中用來取得字串的一個函數，其目的是截取字串的一部分。

  函數的基本語法如下：

  substr(string $string, int $start, int $length = ?) : string
  
  // `$string`: 要截取的原始字串。
  // `$start`: 開始截取的位置，以字元索引表示。
  // `$length`（可選）: 要截取的長度。如果未指定，則截取自 `$start` 至字串結尾的所有字元。

  在剛剛的解法中：

  return substr($firstString, 0, $i);

  substr($firstString, 0, $i)
  用於取得 $firstString 字串的前 0 到 $i-1 的部分，
  這就是找到的最長共同前綴（longest common prefix）。

  例如，如果 $firstString 是 “apple” 而 $i 是 3，
  則 substr($firstString, 0, 3) 將返回 “app”。

LeetCode 傳送門 - Longest Common Prefix