LeetCode 014 Longest Common Prefix

LeetCode

<div>

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:

<pre>Input: strs = ["flower","flow","flight"] Output: "fl" </pre>

Example 2:

<pre>Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings. </pre>

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

</div>

题目大意：

字符串列表的最长前缀

算法思路：

N/A

注意事项：

1. 求最小值len初始值用最大值而不是0
2. char = strs[0][i]而不是char = strs[i]

Python代码：

def longestCommonPrefix(self, strs: List[str]) -> str:
	min_len, res = sys.maxsize, ''
	for s in strs:
		min_len = min(min_len, len(s))
	for i in range(min_len):
		char = strs[0][i]
		same_char = True
		for j in range(1, len(strs)):
			if char != strs[j][i]:
				same_char = False
				break
		if not same_char:
			break
		res += char
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(1)