[已解决]优化空间复杂度

yobdc1

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        i,j = 1,0
        list1 = []
        if len(strs) == 1:
            return strs[0]
        if "" in strs:
            return ""
        while True:
            try:
                if strs[0][j] == strs[i][j]:
                    if i <= len(strs)-2:
                        i += 1
                    else:
                        list1.append(strs[0][j])
                        j += 1
                        i = 1
                else:
                    break
            except IndexError:
                break
            
        if bool(list1) == False:
            return ""
        else:
            c = ''.join(list1)
            return c

最佳答案

月排行榜 / 总排行榜

三体人的智子

2024-8-3 18:58:06

1. class Solution:
   
2.     def longestCommonPrefix(self, strs: List[str]) -> str:
   
3.         if len(strs) == 0:
   
4.             return ""
   
5.         min_length = min(len(s) for s in strs)
   
6.         for i in range(min_length):
   
7.             char = strs[0][i]
   
8.             for j in range(1, len(strs)):
   
9.                 if strs[j][i]!= char:
   
10.                     return strs[0][:i]
    
11.         return strs[0][:min_length]

复制代码

不需要创建list1这个列表来储存共同前缀的字符。

直接比较字符和计算最小长度来找到共同前缀即可。

跳转到最佳答案楼层

FishC

看起来你正在编写一个寻找多个字符串的最长公共前缀的函数，但代码似乎有些混乱，让我们一起理清思路，并且讲一讲如何优化空间复杂度。

### 问题分析
在求解“最长公共前缀”时，我们一般会从第一个字符串开始，然后逐个与其他字符串比较，找出公共前缀。理论上，你只需要保留公共前缀的部分，而不需要额外的存储空间来保存所有字符串的比较结果。

### 优化方案
1. **直接用字符串**：我们可以使用一个简单的变量来存储当前找到的公共前缀，而不是使用额外的列表。
2. **提前返回**：如果某个字符串为空，直接返回空字符串。
3. **完成早期退出**：如果某个字符不匹配，我们可以立即返回当前找到的公共前缀。

下面是优化后的代码：

1. from typing import List
   
2. 
   
3. class Solution:
   
4.     def longestCommonPrefix(self, strs: List[str]) -> str:
   
5.         if not strs:  # 如果输入列表为空
   
6.             return ""
   
7.         
   
8.         prefix = strs[0]  # 先假设第一个字符串是公共前缀
   
9.         
   
10.         for s in strs[1:]:  # 从第二个字符串开始比较
    
11.             while not s.startswith(prefix):  # 如果当前字符串不以prefix开头
    
12.                 prefix = prefix[:-1]  # 去掉prefix的最后一个字符
    
13.                 if not prefix:  # 如果prefix变空
    
14.                     return ""  # 返回空字符串
    
15.         
    
16.         return prefix  # 返回最后确定的公共前缀

复制代码

### 空间复杂度分析
此优化对空间复杂度的影响主要体现在：
- 我们仅使用了`prefix`这个变量来存储公共前缀，而没有使用额外的列表或动态数组。因此，空间复杂度为 O(1)，即常量空间。
  
### 总结
通过使用字符串本身而不是列表，我们显著减少了额外的空间需求。这就像是在生活中，我们经常只需要带少量必要的东西出门，减少负担，让生活更轻松！

希望这段幽默又实用的解释能帮助你更好地理解这个问题！有任何其他疑问，随时问我！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

三体人的智子

1. class Solution:
   
2.     def longestCommonPrefix(self, strs: List[str]) -> str:
   
3.         if len(strs) == 0:
   
4.             return ""
   
5.         min_length = min(len(s) for s in strs)
   
6.         for i in range(min_length):
   
7.             char = strs[0][i]
   
8.             for j in range(1, len(strs)):
   
9.                 if strs[j][i]!= char:
   
10.                     return strs[0][:i]
    
11.         return strs[0][:min_length]

复制代码

不需要创建list1这个列表来储存共同前缀的字符。

直接比较字符和计算最小长度来找到共同前缀即可。