黑马程序员技术交流社区

标题: 字符串数组最长公共序列，了解一下？ [打印本页]

---

作者: 郑成功    时间: 2018-7-30 23:31
标题: 字符串数组最长公共序列，了解一下？
编写一个函数查找字符串数组中最长的公共前缀。
如果不存在公共前缀，则返回空字符串 "" 。
["apple", "append, "apologize"] ==> "fl"
["dog", "animals", "cat"] ==> ""


这是我最近在LeetCode上发现的一道题，感觉还挺有意思的，在这里分享给大家^-^
当时拿到手，想了半天，实在没有太好的解决方法，只能用暴力解决了。
话不多说，跟大家分享一下我的思路：
1.定义一个字符串变量str，初始值为空，用于下面记录公共前缀
2.将列表中的第一个字符串str[0]取出来（其实我是想拿列表中长度最短的字符串，不会，唉......）
3.定义一个整型变量a=len(str[0])，外层for循环用于遍历str[0]长度，用i表示
4.for循环嵌套，内层for循环用于遍历列表长度，用j表示
5.if判断: str[0][j] != str[j] ==> str[0]的第j个字符和
列表中其他字符串同位置的字符不相等==>break跳出内层循环，否则的话继续内层循环
6.用for else结构，如果内层循环for不是通过break结束的，
就说明str[0]的第j个位置字符是公共前缀的一部分，就将该字符添加到str中去。
7.加一个if条件判断，如果内层循环第一次执行过后，str还是一个空字符串，
说明不存在公共前缀，直接break跳出外层循环，否则的话继续执行循环体
8.for嵌套循环执行结束，将str return出来
9.前面提到过，因为从列表中取的是第一个字符串，并不是长度最短的，
所以，如果列表中存在长度与之相比短的，程序可能会报错，但不会影响最终结果
所以我用了try...except...结构，将主代码块放到try中，程序报错时同样会return出str，得到结果。
代码附上：(代码之前写好了，直接copy过来的)
class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        try:
            str = ""
            a = len(strs[0])
            for j in range(0, a):
                for i in range(1, len(strs)):
                    if strs[0][j] != strs[j]:
                        break
                else:
                    str += strs[0][j]
                if len(str) == 0:
                    break
            return str
        except:
            return str


strs = ["flower", "flow", "flight"]
result = Solution()
result_str = result.longestCommonPrefix(strs)   

这就是整个代码块了，如果各位有更好的想法，欢迎到下方来留言，大家一起讨论讨论。
谢谢观看！！！      

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2