Skip to content

Commit c5374f2

Browse files
author
Мето Трајковски
committed
Added more solutions
1 parent 0bf441d commit c5374f2

16 files changed

+467
-17
lines changed

‎Backtracking/find_original_words.py‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
'''
2+
Find Original Words
3+
4+
Given a dictionary of words and a string made up of those words (no spaces), return the original sentence in a list. If there is more than one possible reconstruction, return any of them.
5+
If there is no possible reconstruction, then return null.
6+
7+
Input: sentence = 'thequickbrownfox', words = ['quick', 'brown', 'the', 'fox']
8+
Output: ['the', 'quick', 'brown', 'fox']
9+
10+
Input: sentence = 'bedbathandbeyond', words = ['bed', 'bath', 'bedbath', 'and', 'beyond']
11+
Output: ['bed', 'bath', 'and', 'beyond] or ['bedbath', 'and', 'beyond']
12+
13+
=========================================
14+
Backtracking, iterate the sentence construct a substring and check if that substring exist in the set of words.
15+
If the end is reached but the last word doesn't exist in the words, go back 1 word from the result (backtracking).
16+
Time Complexity: O(N) , (worst case, about O(W! * N), for example sentence='aaaaaac', words=['a','aa','aaa','aaaa','aaaaa', 'aaaaaa'])
17+
Space Complexity: O(W) , W = number of words
18+
'''
19+
20+
21+
############
22+
# Solution #
23+
############
24+
25+
def find_words(sentence, words):
26+
all_words = set()
27+
28+
# create a set from all words
29+
for i in range(len(words)):
30+
all_words.add(words[i])
31+
32+
n = len(sentence)
33+
i = 0
34+
subsentence = ''
35+
result = []
36+
37+
# go letter by letter and save the new letter in subsentence
38+
while (i < n) or (len(subsentence) != 0):
39+
# if there are no left letters in the sentence, then this combination is not valid
40+
# remove the last word from the results and continue from that word
41+
if i == n:
42+
i -= len(subsentence)
43+
# if there are no words in the result, then this string is not composed only from the given words
44+
if len(result) == 0:
45+
return None
46+
subsentence = result[-1]
47+
del result[-1]
48+
49+
# add the new letter into subsentence and remove it from the sentence
50+
subsentence += sentence[i]
51+
i += 1
52+
53+
# check if the new word exist in the set
54+
if subsentence in all_words:
55+
result.append(subsentence)
56+
subsentence = ''
57+
58+
return result
59+
60+
61+
###########
62+
# Testing #
63+
###########
64+
65+
# Test 1
66+
# Correct result => ['the', 'quick', 'brown', 'fox']
67+
print(find_words('thequickbrownfox', ['quick', 'brown', 'the', 'fox']))
68+
69+
# Test 2
70+
# Correct result => ['bed', 'bath', 'and', 'beyond']
71+
print(find_words('bedbathandbeyond', ['bed', 'bath', 'bedbath', 'and', 'beyond']))
72+
73+
# Test 3
74+
# Correct result => ['bed', 'bathand', 'beyond']
75+
print(find_words('bedbathandbeyond', ['bed', 'bath', 'bedbath', 'bathand', 'beyond']))
76+
77+
# Test 4
78+
# Correct result => None ('beyo' doesn't exist)
79+
print(find_words('bedbathandbeyo', ['bed', 'bath', 'bedbath', 'bathand', 'beyond']))

‎Dynamic Programming/climbing_staircase.py‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
'''
2+
Climbing Staircase
3+
4+
There exists a staircase with N steps, and you can climb up either X different steps at a time.
5+
Given N, write a function that returns the number of unique ways you can climb the staircase.
6+
The order of the steps matters.
7+
8+
Input: steps = [1, 2], height = 4
9+
Output: 5
10+
Output explanation:
11+
1, 1, 1, 1
12+
2, 1, 1
13+
1, 2, 1
14+
1, 1, 2
15+
2, 2
16+
17+
=========================================
18+
Dynamic Programing
19+
Time Complexity: O(N*S)
20+
Space Complexity: O(N)
21+
If steps are only [1, 2], this problem can be solved using Fibonacci algorithm, because ways(n) = ways(n-1) + ways(n-2).
22+
Time Complexity: O(Fib(N))
23+
Space Complexity: O(1)
24+
'''
25+
26+
27+
############
28+
# Solution #
29+
############
30+
31+
def climbing_staircase(steps, height):
32+
dp = [0 for i in range(height)]
33+
34+
# add all steps into dp
35+
for s in steps:
36+
if s <= height:
37+
dp[s - 1] = 1
38+
39+
# for each current position look how you can arrive there
40+
for i in range(height):
41+
for s in steps:
42+
if i - s >= 0:
43+
dp[i] += dp[i - s]
44+
45+
return dp[height - 1]
46+
47+
48+
###########
49+
# Testing #
50+
###########
51+
52+
# Test 1
53+
# Correct result => 5
54+
print(climbing_staircase([1, 2], 4))
55+
56+
# Test 2
57+
# Correct result => 3
58+
print(climbing_staircase([1, 3, 5], 4))

‎Dynamic Programming/coin_change.py‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
'''
2+
Coin Change
3+
4+
You are given coins of different denominations and a total amount of money amount.
5+
Write a function to compute the fewest number of coins that you need to make up that amount.
6+
If that amount of money cannot be made up by any combination of the coins, return -1.
7+
8+
Input: coins = [1, 2, 5], amount = 11
9+
Output: 3
10+
11+
Input: coins = [2], amount = 3
12+
Output: -1
13+
14+
=========================================
15+
Dynamic programming solution 1
16+
Time Complexity: O(A*C) , A = amount, C = coins
17+
Space Complexity: O(A)
18+
Dynamic programming solution 2 (don't need the whole array, just use modulo to iterate through the partial array)
19+
Time Complexity: O(A*C) , A = amount, C = coins
20+
Space Complexity: O(maxCoin)
21+
'''
22+
23+
24+
##############
25+
# Solution 1 #
26+
##############
27+
28+
def coin_change_1(coins, amount):
29+
if amount == 0:
30+
return 0
31+
if len(coins) == 0:
32+
return -1
33+
34+
max_value = amount + 1 # use this instead of math.inf
35+
dp = [max_value for i in range(max_value)]
36+
dp[0] = 0
37+
38+
for i in range(1, max_value):
39+
for c in coins:
40+
if c <= i:
41+
# search on previous positions for min coins needed
42+
dp[i] = min(dp[i], dp[i - c] + 1)
43+
44+
if (dp[amount] == max_value):
45+
return -1
46+
return dp[amount]
47+
48+
49+
##############
50+
# Solution 2 #
51+
##############
52+
53+
def coin_change_2(coins, amount):
54+
if amount == 0:
55+
return 0
56+
if len(coins) == 0:
57+
return -1
58+
59+
max_value = amount + 1 # use this instead of math.inf
60+
max_coin = min(max_value, max(coins) + 1)
61+
dp = [max_value for i in range(max_coin)]
62+
dp[0] = 0
63+
64+
for i in range(1, max_value):
65+
i_mod = i % max_coin
66+
dp[i_mod] = max_value # reset current position
67+
68+
for c in coins:
69+
if c <= i:
70+
# search on previous positions for min coins needed
71+
dp[i_mod] = min(dp[i_mod], dp[(i - c) % max_coin] + 1)
72+
73+
if (dp[amount % max_coin] == max_value):
74+
return -1
75+
return dp[amount % max_coin]
76+
77+
78+
###########
79+
# Testing #
80+
###########
81+
82+
# Test 1
83+
# Correct result => 3
84+
print(coin_change_1([1, 2, 5], 11))
85+
print(coin_change_2([1, 2, 5], 11))
86+
87+
# Test 2
88+
# Correct result => -1
89+
print(coin_change_1([2], 3))
90+
print(coin_change_2([2], 3))

‎Linked Lists/add_two_numbers.py‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
'''
2+
Add two numbers
3+
4+
You are given two non-empty linked lists representing two non-negative integers.
5+
The digits are stored in reverse order and each of their nodes contain a single digit.
6+
Add the two numbers and return it as a linked list.
7+
8+
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
9+
10+
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
11+
Output: 7 -> 0 -> 8
12+
Output explanation: 342 + 465 = 807
13+
14+
=========================================
15+
Iterate LL and add values on same position (just like adding real numbers).
16+
Time Complexity: O(N)
17+
Space Complexity: O(1)
18+
'''
19+
20+
21+
############
22+
# Solution #
23+
############
24+
25+
# Definition for singly-linked list.
26+
class ListNode:
27+
def __init__(self, x, n = None):
28+
self.val = x
29+
self.next = n
30+
31+
def add_two_numbers(l1, l2):
32+
start = ListNode(None)
33+
# use the same linked list as result so the Space complexity will be O(1)
34+
start.next = l1
35+
pointer = start
36+
transfer = 0
37+
38+
while (l1 is not None) or (l2 is not None) or (transfer != 0):
39+
v1 = 0
40+
if l1 is not None:
41+
v1 = l1.val
42+
l1 = l1.next
43+
44+
v2 = 0
45+
if l2 is not None:
46+
v2 = l2.val
47+
l2 = l2.next
48+
49+
total = transfer + v1 + v2
50+
transfer = total // 10
51+
52+
if l1 is None:
53+
# if the first list is shorter than the second, add new elements at the end
54+
pointer.next = ListNode(None)
55+
pointer = pointer.next
56+
pointer.val = total % 10
57+
58+
return start.next
59+
60+
61+
###########
62+
# Testing #
63+
###########
64+
65+
# Test 1
66+
# Correct result => 7 -> 0 -> 8
67+
l1 = ListNode(2, ListNode(4, ListNode(3)))
68+
l2 = ListNode(5, ListNode(6, ListNode(4)))
69+
res = add_two_numbers(l1, l2)
70+
st = ''
71+
while res != None:
72+
st += str(res.val) + ' '
73+
res = res.next
74+
print(st)
75+
76+
# Test 2
77+
# Correct result => 8 -> 9 -> 0 -> 0 -> 1
78+
l1 = ListNode(9, ListNode(9, ListNode(9, ListNode(9))))
79+
l2 = ListNode(9, ListNode(9))
80+
res = add_two_numbers(l1, l2)
81+
st = ''
82+
while res != None:
83+
st += str(res.val) + ' '
84+
res = res.next
85+
print(st)

‎Lists/container_with_most_water.py‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
'''
2+
Container With Most Water
3+
4+
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
5+
6+
Input: [1,8,6,2,5,4,8,3,7]
7+
Output: 49
8+
9+
=========================================
10+
Playing with pointers from both sides, eliminate smaller heights and search for a bigger height.
11+
Time Complexity: O(N)
12+
Space Complexity: O(1)
13+
'''
14+
15+
16+
############
17+
# Solution #
18+
############
19+
20+
def max_area(height):
21+
l = 0
22+
r = len(height) - 1
23+
max_height = 0
24+
25+
while l < r:
26+
left = height[l]
27+
right = height[r]
28+
29+
current_height = min(left, right) * (r - l)
30+
max_height = max(max_height, current_height)
31+
32+
# take the smaller side and search for a bigger height on that side
33+
if left < right:
34+
while (l < r) and (left >= height[l]):
35+
l += 1
36+
else:
37+
while (l < r) and (right >= height[r]):
38+
r -= 1
39+
40+
return max_height
41+
42+
43+
###########
44+
# Testing #
45+
###########
46+
47+
# Correct result => 49
48+
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))

0 commit comments

Comments
 (0)