Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/14.html
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.
Constraints:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]
consists of only lowercase English letters.
Algorithm
Algorithm Explanation:
- Initialize two variables,
i
andj
, wherei
will traverse the characters in the search string, andj
will traverse each string in the string set. - Since the words are arranged vertically, it can be considered as a two-dimensional array with unequal line lengths. The traversal order is different from the general horizontal line-by-line traversal. Instead, the vertical traversal is adopted.
- The common prefix that has been found cannot be longer than the shortest word, so the common prefix that has been found is returned at this time.
- Take out the character at a certain position of the first string each time, and then traverse the corresponding positions of all other strings to see if they are equal.
- If any character is not equal, return the result. If all characters are the same, save the current character in the result and continue checking the character in the next position.
Improved Algorithm Explanation:
- Initialize two variables,
i
andj
, wherei
will traverse the characters in the search string, andj
will traverse each string in the string set. - Consider the string set as a 2D array with unequal line lengths, with the characters arranged vertically. Traverse the array vertically instead of horizontally.
- Since the common prefix cannot be longer than the shortest word, return the common prefix once its length equals the length of the shortest word.
- Take out the character at a certain position of the first string each time, and then traverse the corresponding positions of all other strings to see if they are equal.
- If any character is not equal, return the result. If all characters are the same, save the current character in the result and continue checking the character in the next position.
Code
-
public class Longest_Common_Prefix { public class Solution { public String longestCommonPrefix(String[] s) { if (s == null || s.length == 0) { return ""; } int i = 0; StringBuilder result = new StringBuilder(); while (true) { for (String each : s) { if (i >= each.length() || each.charAt(i) != s[0].charAt(i)) { return result.toString(); } } result.append(s[0].charAt(i)); i++; } } } } ############ class Solution { public String longestCommonPrefix(String[] strs) { int n = strs.length; for (int i = 0; i < strs[0].length(); ++i) { for (int j = 1; j < n; ++j) { if (strs[j].length() <= i || strs[j].charAt(i) != strs[0].charAt(i)) { return strs[0].substring(0, i); } } } return strs[0]; } }
-
// OJ: https://leetcode.com/problems/longest-common-prefix/ // Time: O(NW) // Space: O(1) class Solution { public: string longestCommonPrefix(vector<string>& A) { int len = A[0].size(); for (int i = 1; i < A.size() && len; ++i) { int j = 0, end = min(len, (int)A[i].size()); while (j < end && A[0][j] == A[i][j]) ++j; len = j; } return A[0].substr(0, len); } };
-
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: for i in range(len(strs[0])): for s in strs[1:]: if len(s) <= i or s[i] != strs[0][i]: return s[:i] return strs[0] ############ class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if len(strs) == 0: return "" i = 0 j = 0 end = 0 while j < len(strs) and i < len(strs[j]): if j == 0: char = strs[j][i] else: if strs[j][i] != char: break if j == len(strs) - 1: i += 1 j = 0 end += 1 else: j += 1 return strs[j][:end]
-
func longestCommonPrefix(strs []string) string { n := len(strs) for i := range strs[0] { for j := 1; j < n; j++ { if len(strs[j]) <= i || strs[j][i] != strs[0][i] { return strs[0][:i] } } } return strs[0] }
-
function longestCommonPrefix(strs: string[]): string { const len = strs.reduce((r, s) => Math.min(r, s.length), Infinity); for (let i = len; i > 0; i--) { const target = strs[0].slice(0, i); if (strs.every(s => s.slice(0, i) === target)) { return target; } } return ''; }
-
/** * @param {string[]} strs * @return {string} */ var longestCommonPrefix = function (strs) { for (let j = 0; j < strs[0].length; j++) { for (let i = 0; i < strs.length; i++) { if (strs[0][j] !== strs[i][j]) { return strs[0].substring(0, j); } } } return strs[0]; };
-
# @param {String[]} strs # @return {String} def longest_common_prefix(strs) return '' if strs.nil? || strs.length.zero? return strs[0] if strs.length == 1 idx = 0 while idx < strs[0].length cur_char = strs[0][idx] str_idx = 1 while str_idx < strs.length return idx > 0 ? strs[0][0..idx-1] : '' if strs[str_idx].length <= idx return '' if strs[str_idx][idx] != cur_char && idx.zero? return strs[0][0..idx - 1] if strs[str_idx][idx] != cur_char str_idx += 1 end idx += 1 end idx > 0 ? strs[0][0..idx] : '' end
-
using System.Text; using System.Linq; public class Solution { public string LongestCommonPrefix(string[] strs) { if (strs.Length == 0) return string.Empty; var sb = new StringBuilder(); for (var i = 0; i < strs[0].Length; ++i) { var ch = strs[0][i]; if (strs.All(str => str.Length > i && str[i] == ch)) { sb.Append(ch); } else { break; } } return sb.ToString(); } }
-
impl Solution { pub fn longest_common_prefix(strs: Vec<String>) -> String { let mut len = strs.iter().map(|s| s.len()).min().unwrap(); for i in (1..=len).rev() { let mut is_equal = true; let target = strs[0][0..i].to_string(); if strs.iter().all(|s| target == s[0..i]) { return target; } } String::new() } }
-
class Solution { /** * @param String[] $strs * @return String */ function longestCommonPrefix($strs) { $rs = ""; for ($i = 0; $i < strlen($strs[0]); $i++) { for ($j = 1; $j < count($strs); $j++) { if ($strs[0][$i] != $strs[$j][$i]) return $rs; } $rs = $rs.$strs[0][$i]; } return $rs; } }