139. Word Break.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.\n",
    "\n",
    "Note:\n",
    "\n",
    "The same word in the dictionary may be reused multiple times in the segmentation.\n",
    "You may assume the dictionary does not contain duplicate words.\n",
    "Example 1:\n",
    "\n",
    "Input: s = \"leetcode\", wordDict = [\"leet\", \"code\"]\n",
    "Output: true\n",
    "Explanation: Return true because \"leetcode\" can be segmented as \"leet code\".\n",
    "Example 2:\n",
    "\n",
    "Input: s = \"applepenapple\", wordDict = [\"apple\", \"pen\"]\n",
    "Output: true\n",
    "Explanation: Return true because \"applepenapple\" can be segmented as \"apple pen apple\".\n",
    "             Note that you are allowed to reuse a dictionary word.\n",
    "Example 3:\n",
    "\n",
    "Input: s = \"catsandog\", wordDict = [\"cats\", \"dog\", \"sand\", \"and\", \"cat\"]\n",
    "Output: false\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        f=[False for i in range(len(s)+1)]       \n",
    "        f[0]=True\n",
    "        for i in range(1,len(s)+1):\n",
    "            for j in range(i):\n",
    "                if f[j] and s[j:i] in wordDict:\n",
    "                    f[i] = True                 \n",
    "        return f[len(s)]\n",
    "        "
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}