Skip to content

Commit c31f97e

Browse files
author
Мето Трајковски
committed
Added new solutions
1 parent 88c4e7e commit c31f97e

File tree

7 files changed

+225
-11
lines changed

7 files changed

+225
-11
lines changed

‎Backtracking/find_original_words.py‎

Lines changed: 14 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,15 @@
11
'''
2-
Find Original Words
2+
Word Break
33
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.
4+
Given a dictionary of words and a string made up of those words (no spaces), return the original sentence in a list.
5+
If there is more than one possible reconstruction, return solution with less words.
56
If there is no possible reconstruction, then return null.
67
78
Input: sentence = 'thequickbrownfox', words = ['quick', 'brown', 'the', 'fox']
89
Output: ['the', 'quick', 'brown', 'fox']
910
1011
Input: sentence = 'bedbathandbeyond', words = ['bed', 'bath', 'bedbath', 'and', 'beyond']
11-
Output: ['bed', 'bath', 'and', 'beyond] or ['bedbath', 'and', 'beyond']
12+
Output: ['bedbath', 'and', 'beyond'] (['bed', 'bath', 'and', 'beyond] has more words)y
1213
1314
=========================================
1415
Backtracking, iterate the sentence construct a substring and check if that substring exist in the set of words.
@@ -22,6 +23,8 @@
2223
# Solution #
2324
############
2425

26+
from collections import deque
27+
2528
def find_words(sentence, words):
2629
all_words = set()
2730

@@ -32,7 +35,7 @@ def find_words(sentence, words):
3235
n = len(sentence)
3336
i = 0
3437
subsentence = ''
35-
result = []
38+
result = deque()
3639

3740
# go letter by letter and save the new letter in subsentence
3841
while (i < n) or (len(subsentence) != 0):
@@ -44,7 +47,7 @@ def find_words(sentence, words):
4447
if len(result) == 0:
4548
return None
4649
subsentence = result[-1]
47-
del result[-1]
50+
result.pop()
4851

4952
# add the new letter into subsentence and remove it from the sentence
5053
subsentence += sentence[i]
@@ -55,7 +58,7 @@ def find_words(sentence, words):
5558
result.append(subsentence)
5659
subsentence = ''
5760

58-
return result
61+
return list(result)
5962

6063

6164
###########
@@ -76,4 +79,8 @@ def find_words(sentence, words):
7679

7780
# Test 4
7881
# Correct result => None ('beyo' doesn't exist)
79-
print(find_words('bedbathandbeyo', ['bed', 'bath', 'bedbath', 'bathand', 'beyond']))
82+
print(find_words('bedbathandbeyo', ['bed', 'bath', 'bedbath', 'bathand', 'beyond']))
83+
84+
# Test 5
85+
# Correct result => ['314', '15926535897', '9323', '8462643383279']
86+
print(find_words('3141592653589793238462643383279', ['314', '49', '9001', '15926535897', '14', '9323', '8462643383279', '4', '793']))

‎Trees/find_max_branch_sum.py‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
'''
2+
Find max branch sum
3+
4+
Wrie a function that takes a binary tree and returns its max branch (branch is "root to leaf path") sum.
5+
6+
Input:
7+
1
8+
/ \
9+
2 3
10+
/ \ / \
11+
4 5 6 7
12+
Output: 11
13+
Output explanation: 1 -> 3 -> 7
14+
15+
=========================================
16+
Traverse the tree and in each node compare the left and right subbranch sum, and take the bigger one.
17+
Time Complexity: O(N)
18+
Space Complexity: O(N) , because of the recursion stack (but this is the tree is one branch), O(LogN) if the tree is balanced.
19+
'''
20+
21+
22+
############
23+
# Solution #
24+
############
25+
26+
class TreeNode:
27+
def __init__(self, val, left=None, right=None):
28+
self.val = val
29+
self.left = left
30+
self.right = right
31+
32+
def max_branch_sum(node):
33+
if node is None:
34+
return 0
35+
36+
# take the max left subbranch sum and add the current node value
37+
left_max_sum = max_branch_sum(node.left) + node.val
38+
# take the max right subbranch sum and add the current node value
39+
right_max_sum = max_branch_sum(node.right) + node.val
40+
41+
# return the bigger sum
42+
return max(left_max_sum, right_max_sum)
43+
44+
45+
###########
46+
# Testing #
47+
###########
48+
49+
# Test 1
50+
# Correct result => 11
51+
tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
52+
print(max_branch_sum(tree))

‎Trees/find_max_path_sum.py‎

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
'''
2+
Find max path sum
3+
4+
Wrie a function that takes a Binary Tree and returns its max path sum.
5+
6+
Input:
7+
1
8+
/ \
9+
2 3
10+
/ \ / \
11+
4 5 6 7
12+
Output: 18
13+
Output explanation: 5 -> 2 -> 1 -> 3 -> 7
14+
15+
Input:
16+
-1
17+
/ \
18+
-2 3
19+
/ \ / \
20+
-4 -5 2 5
21+
Output: 10
22+
Output explanation: 2 -> 3 -> 5
23+
24+
=========================================
25+
Traverse the tree and in each node compare create a new path where the left and right max subpaths are merging in the current node.
26+
Time Complexity: O(N)
27+
Space Complexity: O(N) , because of the recursion stack (but this is the tree is one branch), O(LogN) if the tree is balanced.
28+
'''
29+
30+
31+
############
32+
# Solution #
33+
############
34+
35+
class TreeNode:
36+
def __init__(self, val, left=None, right=None):
37+
self.val = val
38+
self.left = left
39+
self.right = right
40+
41+
def max_path_sum(tree):
42+
return find_max_path_sum(tree)[0]
43+
44+
def find_max_path_sum(node):
45+
if node is None:
46+
return (0, 0)
47+
48+
# get the result from the left subtree
49+
left_result = find_max_path_sum(node.left)
50+
# get the result from the right subtree
51+
right_result = find_max_path_sum(node.right)
52+
53+
# create a new path by merging the max left and right subpaths
54+
current_path = left_result[1] + node.val + right_result[1]
55+
# find the max path till now, comparing the new path, max path from the left and right subtree
56+
max_path = max(left_result[0], current_path, right_result[0])
57+
# find the max subpath, min value for a subpath sum is 0
58+
max_subpath = max(left_result[1] + node.val, right_result[1] + node.val, node.val, 0)
59+
60+
return (max_path, max_subpath)
61+
62+
63+
###########
64+
# Testing #
65+
###########
66+
67+
# Test 1
68+
# Correct result => 18
69+
tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
70+
print(max_path_sum(tree))
71+
72+
# Test 2
73+
# Correct result => 10
74+
tree = TreeNode(-1, TreeNode(-2, TreeNode(-4), TreeNode(-5)), TreeNode(3, TreeNode(2), TreeNode(5)))
75+
print(max_path_sum(tree))
76+
77+
# Test 3
78+
'''
79+
1
80+
/ \
81+
7 3
82+
/ \ / \
83+
-4 -5 6 2
84+
'''
85+
# Correct result => 17 (7 -> 1 -> 3 -> 6)
86+
tree = TreeNode(1, TreeNode(7, TreeNode(-4), TreeNode(-5)), TreeNode(3, TreeNode(6), TreeNode(2)))
87+
print(max_path_sum(tree))
88+
89+
# Test 4
90+
'''
91+
1
92+
/ \
93+
2 3
94+
/ \ / \
95+
-4 -5 -2 -3
96+
'''
97+
# Correct result => 6 (2 -> 1 -> 3)
98+
tree = TreeNode(1, TreeNode(2, TreeNode(-4), TreeNode(-5)), TreeNode(3, TreeNode(-2), TreeNode(-3)))
99+
print(max_path_sum(tree))

‎Trees/find_second_largest_node.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
=========================================
77
Traverse tree and compare the current value with the saved 2 values.
88
Time Complexity: O(N)
9-
Space Complexity: O(LogN) , because of the recursion stack (but this is if the tree is balanced), worst case O(N) if the tree is one branch.
9+
Space Complexity: O(N) , because of the recursion stack (but this is the tree is one branch), O(LogN) if the tree is balanced.
1010
'''
1111

1212

‎Trees/find_second_largest_node_bst.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,8 +6,8 @@
66
=========================================
77
There are 4 possible cases (see the details in the code).
88
Only 1 branch is searched to the end (leaf), not the whole tree.
9-
Time Complexity: O(LogN) , this is if the tree is balanced (balanced bst), but the worst case will be if all elements are in the one (the right) branch O(N)
10-
Space Complexity: O(LogN) , -||- but this is because of the recursion stack (LogN elements will be in the recursion stack till the leaf is reached)
9+
Time Complexity: O(N) , this is the worst case when all elements are in one (the right) branch O(N), O(LogN) if the tree is balanced (balanced bst)
10+
Space Complexity: O(N) , because of the recursion stack (but this is the tree is one branch), O(LogN) if the tree is balanced.
1111
'''
1212

1313

‎Trees/valid_bst.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
When visiting the left child use the value of the parent node like an upper boundary.
1616
When visiting the right child use the value of the parent node like a lower boundary.
1717
Time Complexity: O(N)
18-
Space Complexity: O(N) - (recursion is used, this complexity is because of stack)
18+
Space Complexity: O(N) , because of the recursion stack (but this is the tree is one branch), O(LogN) if the tree is balanced.
1919
'''
2020

2121
############

‎test.py‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
import math
2+
3+
def solve(sentence, words):
4+
n = len(sentence)
5+
w = len(words)
6+
dp = [math.inf for i in range(n)]
7+
dp[0] = 0
8+
dw = [-1 for i in range(n)]
9+
10+
def solve_2(sentence, words):
11+
n = len(sentence)
12+
w = len(words)
13+
dp = [math.inf for i in range(n + 1)]
14+
dp[0] = 0
15+
dw = [-1 for i in range(n + 1)]
16+
17+
for i in range(1, n + 1):
18+
for j in range(w):
19+
start = i - len(words[j])
20+
if (start >= 0) and (words[j] == sentence[start: i]) and (dp[start] + 1 < dp[i]):
21+
dp[i] = dp[start] + 1
22+
dw[i] = j
23+
24+
if dp[n] == math.inf:
25+
return None
26+
27+
result = ['' for i in range(dp[n])]
28+
i = n
29+
j = dp[n] - 1
30+
while i > 0:
31+
result[j] = words[dw[i]]
32+
i -= len(words[dw[i]])
33+
j -= 1
34+
35+
return result
36+
37+
38+
# Test 1
39+
# Correct result => ['the', 'quick', 'brown', 'fox']
40+
print(solve('thequickbrownfox', ['quick', 'brown', 'the', 'fox']))
41+
42+
# Test 2
43+
# Correct result => ['bed', 'bath', 'and', 'beyond']
44+
print(solve('bedbathandbeyond', ['bed', 'bath', 'bedbath', 'and', 'beyond']))
45+
46+
# Test 3
47+
# Correct result => ['bed', 'bathand', 'beyond']
48+
print(solve('bedbathandbeyond', ['bed', 'bath', 'bedbath', 'bathand', 'beyond']))
49+
50+
# Test 4
51+
# Correct result => None ('beyo' doesn't exist)
52+
print(solve('bedbathandbeyo', ['bed', 'bath', 'bedbath', 'bathand', 'beyond']))
53+
54+
# Test 5
55+
# Correct result => ['314', '15926535897', '9323', '8462643383279']
56+
print(solve('3141592653589793238462643383279', ['314', '49', '9001', '15926535897', '14', '9323', '8462643383279', '4', '793']))

0 commit comments

Comments
 (0)