Skip to content

Commit 24db4c4

Browse files
keonkeon
committed
dp and stuff
1 parent 3dc4e78 commit 24db4c4

8 files changed

Lines changed: 224 additions & 5 deletions

File tree

‎bfs/word_ladder.py‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
"""
2+
Given two words (beginWord and endWord), and a dictionary's word list,
3+
find the length of shortest transformation sequence
4+
from beginWord to endWord, such that:
5+
6+
Only one letter can be changed at a time
7+
Each intermediate word must exist in the word list
8+
For example,
9+
10+
Given:
11+
beginWord = "hit"
12+
endWord = "cog"
13+
wordList = ["hot","dot","dog","lot","log"]
14+
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
15+
return its length 5.
16+
.
17+
Note:
18+
Return 0 if there is no such transformation sequence.
19+
All words have the same length.
20+
All words contain only lowercase alphabetic characters.
21+
"""
22+
def ladderLength(beginWord, endWord, wordList):
23+
"""
24+
Bidirectional BFS!!!
25+
:type beginWord: str
26+
:type endWord: str
27+
:type wordList: Set[str]
28+
:rtype: int
29+
"""
30+
beginSet = set()
31+
endSet = set()
32+
beginSet.add(beginWord)
33+
endSet.add(endWord)
34+
result = 2
35+
while len(beginSet) != 0 and len(endSet) != 0:
36+
if len(beginSet) > len(endSet):
37+
beginSet, endSet = endSet, beginSet
38+
nextBeginSet = set()
39+
for word in beginSet:
40+
for ladderWord in wordRange(word):
41+
if ladderWord in endSet:
42+
return result
43+
if ladderWord in wordList:
44+
nextBeginSet.add(ladderWord)
45+
wordList.remove(ladderWord)
46+
beginSet = nextBeginSet
47+
result += 1
48+
print(beginSet)
49+
print(result)
50+
return 0
51+
52+
def wordRange(word):
53+
for ind in range(len(word)):
54+
tempC = word[ind]
55+
for c in [chr(x) for x in range(ord('a'), ord('z')+1)]:
56+
if c != tempC:
57+
yield word[:ind] + c + word[ind+1:]
58+
59+
beginWord = "hit"
60+
endWord = "cog"
61+
wordList = ["hot","dot","dog","lot","log"]
62+
print(ladderLength(beginWord, endWord, wordList))

divide-and-conquer/expression-add-operators.py renamed to divide-and-conquer/expression_add_operators.py

File renamed without changes.

divide-and-conquer/the-skyline-problem.py renamed to divide-and-conquer/the_skyline_problem.py

File renamed without changes.

‎dp/combination_sum4.py‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
2+
3+
Example:
4+
5+
nums = [1, 2, 3]
6+
target = 4
7+
8+
The possible combination ways are:
9+
(1, 1, 1, 1)
10+
(1, 1, 2)
11+
(1, 2, 1)
12+
(1, 3)
13+
(2, 1, 1)
14+
(2, 2)
15+
(3, 1)
16+
17+
Note that different sequences are counted as different combinations.
18+
19+
Therefore the output is 7.
20+
Follow up:
21+
What if negative numbers are allowed in the given array?
22+
How does it change the problem?
23+
What limitation we need to add to the question to allow negative numbers?
24+
25+
26+
private int[] dp;
27+
28+
public int combinationSum4(int[] nums, int target) {
29+
dp = new int[target + 1];
30+
Arrays.fill(dp, -1);
31+
dp[0] = 1;
32+
return helper(nums, target);
33+
}
34+
35+
private int helper(int[] nums, int target) {
36+
if (dp[target] != -1) {
37+
return dp[target];
38+
}
39+
int res = 0;
40+
for (int i = 0; i < nums.length; i++) {
41+
if (target >= nums[i]) {
42+
res += helper(nums, target - nums[i]);
43+
}
44+
}
45+
dp[target] = res;
46+
return res;
47+
}
48+
49+
50+
EDIT: The above solution is top-down. How about a bottom-up one?
51+
52+
public int combinationSum4(int[] nums, int target) {
53+
int[] comb = new int[target + 1];
54+
comb[0] = 1;
55+
for (int i = 1; i < comb.length; i++) {
56+
for (int j = 0; j < nums.length; j++) {
57+
if (i - nums[j] >= 0) {
58+
comb[i] += comb[i - nums[j]];
59+
}
60+
}
61+
}
62+
return comb[target];
63+
}

‎stack/simplify_path.py‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
"""
2+
Given an absolute path for a file (Unix-style), simplify it.
3+
4+
For example,
5+
path = "/home/", => "/home"
6+
path = "/a/./b/../../c/", => "/c"
7+
8+
* Did you consider the case where path = "/../"?
9+
In this case, you should return "/".
10+
* Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
11+
In this case, you should ignore redundant slashes and return "/home/foo".
12+
"""
13+
14+
def simplify_path(path):
15+
"""
16+
:type path: str
17+
:rtype: str
18+
"""
19+
skip = set(['..','.',''])
20+
stack = []
21+
paths = path.split('/')
22+
for tok in paths:
23+
if tok == '..':
24+
if stack:
25+
stack.pop()
26+
elif tok not in skip:
27+
stack.append(tok)
28+
return '/' +'/'.join(stack)
29+
30+
p = '/my/name/is/..//keon'
31+
print(p)
32+
print(simplify_path(p))

‎string/int_to_roman.py‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
"""
2+
Given an integer, convert it to a roman numeral.
3+
Input is guaranteed to be within the range from 1 to 3999.
4+
"""
5+
6+
def int_to_roman(num):
7+
"""
8+
:type num: int
9+
:rtype: str
10+
"""
11+
M = ["", "M", "MM", "MMM"];
12+
C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
13+
X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
14+
I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
15+
return M[num//1000] + C[(num%1000)//100] + X[(num%100)//10] + I[num%10];
16+
17+
print(int_to_roman(644))

‎string/roman_to_int.py‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
"""
2+
Given a roman numeral, convert it to an integer.
3+
Input is guaranteed to be within the range from 1 to 3999.
4+
"""
5+
6+
7+
def roman_to_int(s):
8+
"""
9+
:type s: str
10+
:rtype: int
11+
"""
12+
number = 0
13+
roman = {'M':1000, 'D':500, 'C': 100, 'L':50, 'X':10, 'V':5, 'I':1}
14+
for i in range(len(s)-1):
15+
if roman[s[i]] < roman[s[i+1]]:
16+
number -= roman[s[i]]
17+
else:
18+
number += roman[s[i]]
19+
return number + roman[s[-1]]
20+
21+
r = "DCXXI"
22+
print(roman_to_int(r))

‎trie/add_and_search.py‎

Lines changed: 28 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -13,12 +13,13 @@
1313
search(“.ad”) -> true
1414
search(“b..”) -> true
1515
"""
16+
import collections
1617

1718
class TrieNode(object):
18-
def __init__(self, letter, isTerminal=False):
19+
def __init__(self, letter, is_terminal=False):
1920
self.children = dict()
2021
self.letter = letter
21-
self.isTerminal = isTerminal
22+
self.is_terminal = is_terminal
2223

2324
class WordDictionary(object):
2425
def __init__(self):
@@ -30,7 +31,7 @@ def addWord(self, word):
3031
if letter not in cur.children:
3132
cur.children[letter] = TrieNode(letter)
3233
cur = cur.children[letter]
33-
cur.isTerminal = True
34+
cur.is_terminal = True
3435

3536
def search(self, word, node=None):
3637
cur = node
@@ -41,7 +42,7 @@ def search(self, word, node=None):
4142
if letter == ".":
4243
if i == len(word) - 1: # if last character
4344
for child in cur.children.itervalues():
44-
if child.isTerminal:
45+
if child.is_terminal:
4546
return True
4647
return False
4748
for child in cur.children.itervalues():
@@ -52,5 +53,27 @@ def search(self, word, node=None):
5253
if letter not in cur.children:
5354
return False
5455
cur = cur.children[letter]
55-
return cur.isTerminal
56+
return cur.is_terminal
5657

58+
class WordDictionary2(object):
59+
def __init__(self):
60+
self.word_dict = collections.defaultdict(list)
61+
62+
63+
def addWord(self, word):
64+
if word:
65+
self.word_dict[len(word)].append(word)
66+
67+
def search(self, word):
68+
if not word:
69+
return False
70+
if '.' not in word:
71+
return word in self.word_dict[len(word)]
72+
for v in self.word_dict[len(word)]:
73+
# match xx.xx.x with yyyyyyy
74+
for i, ch in enumerate(word):
75+
if ch != v[i] and ch != '.':
76+
break
77+
else:
78+
return True
79+
return False

0 commit comments

Comments
 (0)