solution_python/014 Longest Common Prefix.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 014 Longest Common Prefix\n",
    "- 笔记作者：CV七少\n",
    "- 学习时间：2020.6.18\n",
    "- 编程语言：python\n",
    "- 学习任务：leetcode题解\n",
    "- 题目地址：https://leetcode-cn.com/problems/longest-common-prefix/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目:\n",
    "\n",
    "编写一个函数来查找字符串数组中的最长公共前缀。\n",
    "\n",
    "如果不存在公共前缀，返回空字符串` \"\" `。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 示例：\n",
    "- 示例 1:\n",
    "    ```\n",
    "    输入: [\"flower\",\"flow\",\"flight\"]\n",
    "    输出: \"fl\"\n",
    "    ```\n",
    "- 示例 2:\n",
    "    ```\n",
    "    输入: [\"dog\",\"racecar\",\"car\"]\n",
    "    输出: \"\"\n",
    "    解释: 输入不存在公共前缀。\n",
    "    ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法一：**</font> 水平扫描\n",
    "```\n",
    "执行用时：36 ms, 在所有 Python3 提交中击败了93.16%的用户\n",
    "内存消耗：13.7 MB, 在所有 Python3 提交中击败了6.15%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为: fl\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(strs) == 0:\n",
    "            return ''\n",
    "        s = min(strs, key = len)\n",
    "        for i in range(0, len(strs)):\n",
    "            while strs[i].find(s) != 0 :\n",
    "                s = s[:-1]\n",
    "        return s\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:   strs = [\"flower\",\"flow\",\"flight\"]\n",
    "               output:   \"fl\"\n",
    "\"\"\"\n",
    "strs = [\"flower\",\"flow\",\"flight\"]\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.longestCommonPrefix(strs)\n",
    "print('输出为:', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法二：**</font> 垂直扫描\n",
    "```\n",
    "执行用时：56 ms, 在所有 Python3 提交中击败了13.31%的用户\n",
    "内存消耗：13.7 MB, 在所有 Python3 提交中击败了6.15%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为: fl\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(strs) == 0:\n",
    "            return ''\n",
    "        s = min(strs, key=len)\n",
    "        for i in range(len(s)):\n",
    "            ch = s[i]\n",
    "            for j in range(len(strs)):\n",
    "                if strs[j][i] != ch:\n",
    "                    return s[:i]\n",
    "        return s\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:   strs = [\"flower\",\"flow\",\"flight\"]\n",
    "               output:   \"fl\"\n",
    "\"\"\"\n",
    "strs = [\"flower\",\"flow\",\"flight\"]\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.longestCommonPrefix(strs)\n",
    "print('输出为:', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法三：**</font> 最小最大字符串   \n",
    "先找出数组中字典序最小和最大的字符串，最长公共前缀即为这两个字符串的公共前缀\n",
    "```\n",
    "执行用时 :44 ms, 在所有 Python3 提交中击败了59.87%的用户\n",
    "内存消耗 :13.6 MB, 在所有 Python3 提交中击败了6.15%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为: fl\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not strs: return \"\"\n",
    "        str0 = min(strs)\n",
    "        str1 = max(strs)\n",
    "        for i in range(len(str0)):\n",
    "            if str0[i] != str1[i]:\n",
    "                return str0[:i]\n",
    "        return str0\n",
    "    \n",
    "\"\"\"\n",
    "For Example:    input:   strs = [\"flower\",\"flow\",\"flight\"]\n",
    "               output:   \"fl\"\n",
    "\"\"\"\n",
    "strs = [\"flower\",\"flow\",\"flight\"]\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.longestCommonPrefix(strs)\n",
    "print('输出为:', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法四：**</font> zip方法  \n",
    "使用 zip 根据字符串下标合并成数组,判断合并后数组里元素是否都相同\n",
    "```\n",
    "执行用时：36 ms, 在所有 Python3 提交中击败了92.78%的用户\n",
    "内存消耗：13.8 MB, 在所有 Python3 提交中击败了6.15%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为: fl\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def longestCommonPrefix(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        ans = ''\n",
    "        for i in zip(*strs):\n",
    "            if len(set(i)) == 1:\n",
    "                ans += i[0]\n",
    "            else:\n",
    "                break\n",
    "        return ans\n",
    "    \n",
    "\"\"\"\n",
    "For Example:    input:   strs = [\"flower\",\"flow\",\"flight\"]\n",
    "               output:   \"fl\"\n",
    "\"\"\"\n",
    "strs = [\"flower\",\"flow\",\"flight\"]\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.longestCommonPrefix(strs)\n",
    "print('输出为:', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "1. https://leetcode-cn.com/problems/longest-common-prefix/solution/pythonchui-zhi-sao-miao-fa-by-mu-qian-ruo-chi/\n",
    "2. https://leetcode-cn.com/problems/longest-common-prefix/solution/zi-dian-xu-zui-da-he-zui-xiao-zi-fu-chuan-de-gong-/\n",
    "3. https://leetcode-cn.com/problems/longest-common-prefix/solution/shi-yong-zip-ji-xing-dai-ma-jian-dan-gao-ding-pyth/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 如果你觉得有用的话：\n",
    "- 请点点 **star** 呦\n",
    "- 关注我的 [CSDN博客](https://mp.csdn.net/console/article)\n",
    "- 关注我的 [哔哩哔哩](https://space.bilibili.com/424394389/channel/detail?cid=132513)\n",
    "- 关注公众号：CV伴读社\n",
    "<img src='./images/qrcode.jpg' style='zoom:100%'>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}