solution_python/030 Substring with Concatenation of All Words.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 030 Substring with Concatenation of All Words\n",
    "- 笔记作者：CV七少\n",
    "- 学习时间：2020.7.14\n",
    "- 编程语言：python\n",
    "- 学习任务：leetcode题解\n",
    "- 题目地址：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目:\n",
    "给定一个字符串` s `和一些长度相同的单词 words。找出` s `中恰好可以由` words `中所有单词串联形成的子串的起始位置。注意子串要与` words `中的单词完全匹配，中间不能有其他字符，但不需要考虑` words `中单词串联的顺序。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 示例：\n",
    "- 示例 1:\n",
    "    ```\n",
    "    输入：s = \"barfoothefoobarman\", words = [\"foo\",\"bar\"]\n",
    "    输出：[0,9]\n",
    "    解释：从索引 0 和 9 开始的子串分别是 \"barfoo\" 和 \"foobar\" 。输出的顺序不重要, [9,0] 也是有效答案。\n",
    "    ```\n",
    "- 示例 2:\n",
    "    ```\n",
    "    输入：s = \"wordgoodgoodgoodbestword\", words = [\"word\",\"good\",\"best\",\"word\"]\n",
    "    输出：[]\n",
    "    ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法一：**</font> 因为单词长度固定的，我们可以计算出截取字符串的单词个数是否和 words 里相等，所以我们可以借用哈希表。\n",
    "一个是哈希表是 words，一个哈希表是截取的字符串，比较两个哈希是否相等！因为遍历和比较都是线性的，所以时间复杂度：O(n^2)\n",
    " [题解](https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/chuan-lian-suo-you-dan-ci-de-zi-chuan-by-powcai/)\n",
    "```\n",
    "执行用时：944 ms, 在所有 Python3 提交中击败了43.29%的用户\n",
    "内存消耗：14 MB, 在所有 Python3 提交中击败了9.52%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： [0, 9]\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        if not s or not words:return []\n",
    "        one_word = len(words[0])\n",
    "        all_len = len(words) * one_word\n",
    "        n = len(s)\n",
    "        words = Counter(words)\n",
    "        res = []\n",
    "        for i in range(0, n - all_len + 1):\n",
    "            tmp = s[i:i+all_len]\n",
    "            c_tmp = []\n",
    "            for j in range(0, all_len, one_word):\n",
    "                c_tmp.append(tmp[j:j+one_word])\n",
    "            if Counter(c_tmp) == words:\n",
    "                res.append(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:  s = \"barfoothefoobarman\", words = [\"foo\",\"bar\"]\n",
    "               output:  [0,9]\n",
    "\"\"\"\n",
    "s = \"barfoothefoobarman\"\n",
    "words = [\"foo\",\"bar\"]\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.findSubstring(s, words)\n",
    "print('输出为：',result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法二：**</font> 滑动窗口！我们一直在 s 维护着所有单词长度总和的一个长度队列！时间复杂度：O(n)[题解](https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/chuan-lian-suo-you-dan-ci-de-zi-chuan-by-powcai/)\n",
    "```\n",
    "执行用时：164 ms, 在所有 Python3 提交中击败了77.36%的用户\n",
    "内存消耗：13.8 MB, 在所有 Python3 提交中击败了9.52%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： [0, 9]\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        if not s or not words:return []\n",
    "        one_word = len(words[0])\n",
    "        word_num = len(words)\n",
    "        n = len(s)\n",
    "        words = Counter(words)\n",
    "        res = []\n",
    "        for i in range(0, one_word):\n",
    "            cur_cnt = 0\n",
    "            left = i\n",
    "            right = i\n",
    "            cur_Counter = Counter()\n",
    "            while right + one_word <= n:\n",
    "                w = s[right:right + one_word]\n",
    "                right += one_word\n",
    "                cur_Counter[w] += 1\n",
    "                cur_cnt += 1\n",
    "                while cur_Counter[w] > words[w]:\n",
    "                    left_w = s[left:left+one_word]\n",
    "                    left += one_word\n",
    "                    cur_Counter[left_w] -= 1\n",
    "                    cur_cnt -= 1\n",
    "                if cur_cnt == word_num :\n",
    "                    res.append(left)\n",
    "        return res\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:  s = \"barfoothefoobarman\", words = [\"foo\",\"bar\"]\n",
    "               output:  [0,9]\n",
    "\"\"\"\n",
    "s = \"barfoothefoobarman\"\n",
    "words = [\"foo\",\"bar\"]\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.findSubstring(s, words)\n",
    "print('输出为：',result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法三：**</font> 该方法是对方法二的优化, 加入一定的剪枝 [题解](https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/chuan-lian-suo-you-dan-ci-de-zi-chuan-by-powcai/)\n",
    "```\n",
    "执行用时：80 ms, 在所有 Python3 提交中击败了91.01%的用户\n",
    "内存消耗：13.9 MB, 在所有 Python3 提交中击败了9.52%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： [0, 9]\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        if not s or not words:return []\n",
    "        one_word = len(words[0])\n",
    "        word_num = len(words)\n",
    "        n = len(s)\n",
    "        if n < one_word:return []\n",
    "        words = Counter(words)\n",
    "        res = []\n",
    "        for i in range(0, one_word):\n",
    "            cur_cnt = 0\n",
    "            left = i\n",
    "            right = i\n",
    "            cur_Counter = Counter()\n",
    "            while right + one_word <= n:\n",
    "                w = s[right:right + one_word]\n",
    "                right += one_word\n",
    "                if w not in words:\n",
    "                    left = right\n",
    "                    cur_Counter.clear()\n",
    "                    cur_cnt = 0\n",
    "                else:\n",
    "                    cur_Counter[w] += 1\n",
    "                    cur_cnt += 1\n",
    "                    while cur_Counter[w] > words[w]:\n",
    "                        left_w = s[left:left+one_word]\n",
    "                        left += one_word\n",
    "                        cur_Counter[left_w] -= 1\n",
    "                        cur_cnt -= 1\n",
    "                    if cur_cnt == word_num :\n",
    "                        res.append(left)\n",
    "        return res\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:  s = \"barfoothefoobarman\", words = [\"foo\",\"bar\"]\n",
    "               output:  [0,9]\n",
    "\"\"\"\n",
    "s = \"barfoothefoobarman\"\n",
    "words = [\"foo\",\"bar\"]\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.findSubstring(s, words)\n",
    "print('输出为：',result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "1. https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/chuan-lian-suo-you-dan-ci-de-zi-chuan-by-powcai/"
   ]
  },
  {
   "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
}