531_stack.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 784. Letter Case Permutation\n",
    "\n",
    "Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.  Return a list of all possible strings we could create."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def letterCasePermutation(S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        r = []\n",
    "        if len(S) == 0:\n",
    "            return ['']\n",
    "        def trie(S, string, r):\n",
    "            if ord(S[0]) >= 48 and ord(S[0]) <= 57:\n",
    "                string += S[0]\n",
    "                if len(S) == 1:\n",
    "                    r.append(string)\n",
    "                else:\n",
    "                    trie(S[1:], string, r)\n",
    "            else:\n",
    "                chars = {S[0].lower(), S[0].upper()}\n",
    "                for char in chars:\n",
    "                    newstring = string[:]\n",
    "                    newstring += char\n",
    "                    if len(S) == 1:\n",
    "                        r.append(newstring)\n",
    "                    else:\n",
    "                        trie(S[1:], newstring, r)\n",
    "            return \n",
    "        trie(S, '', r)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def letterCasePermutation(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        res = ['']\n",
    "        for c in S:\n",
    "            if c.isalpha():\n",
    "                res = [j+i for i in [c.upper(), c.lower()] for j in res]\n",
    "            else:\n",
    "                res = [i+c for i in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 78. Subsets\n",
    "\n",
    "Given a set of distinct integers, nums, return all possible subsets (the power set).\n",
    "\n",
    "Note: The solution set must not contain duplicate subsets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# DFS recursively \n",
    "def subsets1(self, nums):\n",
    "    res = []\n",
    "    self.dfs(sorted(nums), 0, [], res)\n",
    "    return res\n",
    "    \n",
    "def dfs(self, nums, index, path, res):\n",
    "    res.append(path)\n",
    "    for i in range(index, len(nums)):\n",
    "        self.dfs(nums, i+1, path+[nums[i]], res)\n",
    "        \n",
    "# Bit Manipulation    \n",
    "def subsets2(nums):\n",
    "    res = []\n",
    "    nums.sort()\n",
    "    for i in range(1<<len(nums)):\n",
    "        tmp = []\n",
    "        for j in range(len(nums)):\n",
    "            if i & 1 << j:  # if i >> j & 1:\n",
    "                tmp.append(nums[j])\n",
    "        res.append(tmp)\n",
    "    return res\n",
    "    \n",
    "# Iteratively\n",
    "def subsets(snums):\n",
    "    res = [[]]\n",
    "    for num in sorted(nums):\n",
    "        res += [item+[num] for item in res]\n",
    "        print(res)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 526. Beautiful Arrangement\n",
    "\n",
    "Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:\n",
    "\n",
    "The number at the ith position is divisible by i.\n",
    "i is divisible by the number at the ith position.\n",
    "Now given N, how many beautiful arrangements can you construct?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def countArrangement(N):  ## exceed time limit\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        full = set(range(1, N+1))\n",
    "        def trie(full, string, count):\n",
    "            for element in full - set(string):\n",
    "                newstring = string[:]\n",
    "                if element % (len(string) + 1) == 0 or (len(string) + 1) % element == 0:\n",
    "                    newstring += [element]\n",
    "                    if len(newstring) == N:\n",
    "                        count += 1\n",
    "                    else:\n",
    "                        count = trie(full, newstring, count)\n",
    "            return count\n",
    "        count = 0\n",
    "        return trie(full, [], count)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def countArrangement(N):  \n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.count = 0\n",
    "        self.helper([], list(range(1, N + 1)))\n",
    "        return self.count\n",
    "\n",
    "    def helper(self, used_values, rest_values):\n",
    "        i = len(used_values) + 1\n",
    "        if len(rest_values) == 0:\n",
    "            self.count += 1\n",
    "\n",
    "        for each in rest_values:\n",
    "            if i % each == 0 or each % i == 0:\n",
    "                used_values.append(i)\n",
    "                new_rest = rest_values[:]\n",
    "                new_rest.remove(each)\n",
    "                self.helper(used_values, new_rest)\n",
    "                used_values.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 77. Combinations\n",
    "\n",
    "Given two integers n and k, return all possible combinations of k numbers out of 1 ... n."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def combine(n, k):   # problematic... don't know why\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"        \n",
    "        res = []\n",
    "        full = list(range(1, n + 1))\n",
    "        def helper(used_values, k):\n",
    "            if len(used_values) == k:\n",
    "                res.append(used_values)\n",
    "                return res\n",
    "            if len(used_values) == 0:\n",
    "                rest_values = full\n",
    "            else:\n",
    "                rest_values = full[used_values[-1]:]\n",
    "\n",
    "            for each in rest_values:\n",
    "                used_values.append(each)\n",
    "                print(used_values)\n",
    "                res = helper(used_values, k)\n",
    "                used_values.pop()\n",
    "            return \n",
    "        helper([], k)\n",
    "        return res\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def combine(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"        \n",
    "        ans = []\n",
    "        stack = []\n",
    "        x = 1\n",
    "        while True:\n",
    "            l = len(stack)\n",
    "            if l == k:\n",
    "                ans.append(stack[:])\n",
    "            if l == k or x > n - k + l + 1:\n",
    "                if not stack:\n",
    "                    return ans\n",
    "                x = stack.pop() + 1\n",
    "            else:\n",
    "                stack.append(x)\n",
    "                x += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools import combinations   ## interesting....\n",
    "\n",
    "class Solution(object):\n",
    "    def combine(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        return list(combinations(range(1,n+1),k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 79. Word Search\n",
    "\n",
    "Given a 2D board and a word, find if the word exists in the grid.\n",
    "\n",
    "The word can be constructed from letters of sequentially adjacent cell, where \"adjacent\" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def is_valid(self, i, j, board):\n",
    "        m, n  = len(board), len(board[0])\n",
    "        if i < 0 or j < 0 or i >= m or j >= n:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def dfs(self, i, j, k, visited, board, word):\n",
    "        if (i, j) in visited:\n",
    "            return False\n",
    "\n",
    "        if board[i][j] != word[k]:\n",
    "            return False\n",
    "\n",
    "        if k + 1 == len(word):\n",
    "            return True\n",
    "\n",
    "        visited.add((i, j))\n",
    "        directions = {(1, 0), (-1, 0), (0, 1), (0, -1)}\n",
    "        for d in directions:\n",
    "            ni, nj = i + d[0], j + d[1]\n",
    "            if self.is_valid(ni, nj, board) and self.dfs(ni, nj, k+1, visited, board, word):\n",
    "                return True\n",
    "        visited.remove((i, j))\n",
    "\n",
    "        return False\n",
    "\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not board or not board[0]:\n",
    "            return False\n",
    "\n",
    "        m, n  = len(board), len(board[0])\n",
    "        for i in xrange(m):\n",
    "            for j in xrange(n):\n",
    "                visited = set()\n",
    "                if self.dfs(i, j, 0, visited, board, word):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    \n",
    "    def check(self, board, word):\n",
    "        b = []\n",
    "        w = []\n",
    "        for row in range(len(board)):\n",
    "            for col in range(len(board[0])):\n",
    "                b.append(board[row][col])\n",
    "                \n",
    "        for i in word:\n",
    "            w.append(i)\n",
    "        i = 0\n",
    "        while i in range(len(w)):\n",
    "            if w[i] in b:\n",
    "                b.remove(w[i])\n",
    "                w.remove(w[i])\n",
    "            else:\n",
    "                return False\n",
    "        if not w:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def dfs(self, board, word, row, col):\n",
    "        first = word[0]\n",
    "        word = word[1:]\n",
    "        if len(word) == 0:\n",
    "            return True\n",
    "        board[row][col] = ' '\n",
    "        row_next = row + 1\n",
    "        row_last = row - 1\n",
    "        col_next = col + 1\n",
    "        col_last = col - 1\n",
    "        if row_next < len(board) and word[0] == board[row_next][col]:\n",
    "            if self.dfs(board, word, row_next, col):\n",
    "                return True\n",
    "        if row_last >= 0 and word[0] == board[row_last][col]:\n",
    "            if self.dfs(board, word, row_last, col):\n",
    "                return True\n",
    "        if col_next < len(board[0]) and word[0] == board[row][col_next]:\n",
    "            if self.dfs(board, word, row, col_next):\n",
    "                return True\n",
    "        if col_last >= 0 and word[0] == board[row][col_last]:\n",
    "            if self.dfs(board, word, row, col_last):\n",
    "                return True\n",
    "        board[row][col] = first\n",
    "        return False\n",
    "    \n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not word:\n",
    "            return True\n",
    "        if not board or len(board) == 0 or len(board[0]) == 0:\n",
    "            return False\n",
    "        if len(word) > len(board)*len(board[0]):\n",
    "            return False\n",
    "        if self.check(board, word) == False:\n",
    "            return False\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if word[0] == board[i][j]:\n",
    "                    if self.dfs(board, word, i, j):\n",
    "                        return True\n",
    "        return False"
   ]
  }
 ],
 "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}