Leetcode: Strings

Question 1

3. Longest substring with repeating characters

Given a string s, find the length of the longest substring without repeating characters.

Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Answer 1

Double for loop is brute force.

1. Dictionary to get linear time key, value = letter, index
2. Sliding window, need a variable to account for the beginning of the sliding window, for loop handles tail end
3. Calculate length on each iteration
4. Modify sliding window each time a letter is already in the dictionary and key-value is greater than the start index
5. Update the key-value per letter each loop
6. Need a <= comparison for the start/usedChar dictionary so it triggers on “a…a” and doesn’t count “a” twice

Time = O(N)
Space = O(26), constant since we have 26 characters in the alphabet

class Solution:

• —def lengthOfLongestSubstring(self, s: str) -> int:
• ——-seen = {}
• ——-ans = 0
• ——-start = 0
• ——-for i, x in enumerate(s):
• ———–if x in seen and start <= seen[x]:
• —————start = seen[x] + 1
• ———–else:
• —————cur = i - start + 1
• —————ans = max(ans, cur)
• ———–seen[x] = i
• ——-return ans

Question 2

Falling dominos

Given a string with the initial condition of dominoes, where:

. represents that the domino is standing still
L represents that the domino is falling to the left side
R represents that the domino is falling to the right side

Figure out the final position of the dominoes. If there are dominoes that get pushed on both ends, the force cancels out and that domino remains upright.

dominos = "..R..LL..R."
answer = ..RRLLL..RR

Answer 2

you can do this in a very methodical way in which you get 2 lists of left and rights, then once you get the lists you can iterate through them to create a final list by going right, then left

1. KEY!! understand forcing functions in code. Using indexes and a trigger of the force, the initial index is equal to max_force, then each index after you subtract 1 from the force.
2. If there is an opposing force, then you do the opposite in the opposite range(len(list)-1, -1, -1)
3. This will ultimately end up with when the forces collide, the superior force will either be 0 (neutral) positive (forward force) negative (backwards force)
4. if a forward-facing force meets the index of a backwards-facing force, the forward force becomes 0

time: O(n), 3n because we loop through it forward, backwards, and again to make the final string
space: O(n), 2n because we have the force list and the response list. response list helps us reduce the string appending to linear time vs quadradic (confirm with documentation)

class Solution:

• —def answer(self, n):
• ——-force = [0]*len(n)
• ——-f=0
• ——-for i in range(len(n)):
• ———–if n[i]==”R”:
• —————f=len(n)
• ———–elif n[i]==”L”:
• —————f=0
• ———–else:
• —————f=max(0, f-1)
• ———–force[i]+=f
• ——-fl=0
• ——-for i in range(len(n)-1, -1, -1):
• ———–if n[i]==”L”:
• —————fl=-len(n)
• ———–elif n[i]==”R”:
• —————fl=0
• ———–else:
• —————fl=min(fl+1, 0)
• ———–force[i]+=fl
• ——-response=[]
• ——-for x in force:
• ———–if x>0:
• —————response.append(“R”)
• ———–elif x<0:
• —————response.append(“L”)
• ———–else:
• —————response.append(“.”)
• ——-return ““.join(response)

Question 3

list strategies for strings

Answer 3

1. two pointers are a good idea if the list or string is sorted

Question 4

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

Input: s = “leetcode”
Output: 0
Example 2:

Input: s = “loveleetcode”
Output: 2

Answer 4

class Solution:

• —def firstUniqChar(self, s: str) -> int:
• ——-m={}
• ——-for i, x in enumerate(s):
• ———–if x not in m:
• —————m[x]=False
• ———–else:
• —————m[x]=True
• ——-for i,x in enumerate(s):
• ———–if not m[x]:
• —————return i
• ——-return -1

time: O(n), double loop,
space: O(26), constant time bc we use a hashmap with alphabet keys

Question 5

validate parenthesis

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order

Answer 5

1. haspmap + stack
2. create a map with k/v as the opening/closing of the brackets
3. if item in hashmap, add it to stack, else check if stack has items, then pop the last item off thestack and compare it to the k/v pair of the current item.
4. to be valid, at step 3 they have to be equal
5. if the stack has items in it at the end, it is also false so check for that

time: linear
space: linear

class Solution:

• —def fav(self, s):
• ——-_map={“{“: “}”, “(“: “)”, “[”: “]”}
• ——-stack=[]
• ——-for i in s:
• ———–if s in _map:
• —————stack.append(s)
• ———–elif not stack or _map[stack.pop()]!=i:
• —————return False
• ——-return not stack
• —def reverse(self, s: str) -> bool:
• ——-_map={“}”: “{“, “)”: “(“, “]”: “[”}
• ——-stack=[]
• ——-for i in s:
• ———–if i in _map:
• —————if not stack:
• ——————-return False
• —————if stack and stack.pop()!=_map[i]:
• ——————-return False
• ———–else:
• —————stack.append(i)
• ——-return not stack

Question 6

generate parenthesis

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:

Input: n = 1
Output: [”()”]

Answer 6

brute force is to get all possible permutations, check if they are valid, then return the valid ones. Returning the cartesian products (permutations) of N items with a total length of S is N^S. time and space are 2^(2N) here

class Solution:

• —def brute(self, n: int):
• ——-s=”()”
• ——-temp=set()
• ——-for p in itertools.product(s, repeat=n*2):
• ———–temp.add(““.join(p))
• ——-output=[]
• ——-for x in temp:
• ———–if self.validate(x):
• —————output.append(x)
• ——-return output
• —def validate(self, s):
• ——-_map={“(“:”)”}
• ——-stack=[]
• ——-for i in s:
• ———–if i in _map:
• —————stack.append(i)
• ———–elif not stack or _map[stack.pop()]!=i:
• —————return False
• ——-return not stack

1. backtracking
2. to build a valid parenthesis, the opening brackets must be equal to n, same with closing, and there can never be more closing than opening at any time
3. backtracking means that if we move forward with a step and it does not work, we can easily go backwards.
4. to do this, we check if openings

time: O(4^n / n^0.5) Catalan number, which is 4^n / (n^1.5), and for each iteration, we have to append something of N length, so it increases it to 4^n / n^0.5. Realistically, if you gave 2^2n * n it would be acceptable.
space: same as above, we must store each answer which is the catalan number, and each catalan number is N length so multiply them you get O(4^n / n^0.5)

• —def generateParenthesis(self, n):
• ——-self.answer = []
• ——-self.backtrack([], 0, 0, n)
• ——-return self.answer
• —def backtrack(self, current, openings, closings, n):
• ——-if len(current) == 2*n:
• ———–self.answer.append(““.join(current[:]))
• ——-else:
• ———–if openings [less than] n:
• —————current.append(“(“)
• —————self.backtrack(current, openings+1, closings, n)
• —————current.pop()
• ———–if closings [less than] openings:
• —————current.append(“)”)
• —————self.backtrack(current, openings, closings+1, n)
• —————current.pop()

Question 7

Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Answer 7

brute force/intuition is backtracking

1. BACKTRACKING
2. make hashmap of number/letter combos
3. the backtracking method takes the current index of the input string and the current list
4. each method loops through its respective letter combinations, so if input=”23”, the first method only loops through “2” letters
5. stop when len(current)=len(digits) or index>=len(digits)
6. don’t forget to wrap in an if/else since the backtracking basecase doesn’t return anything

time: O((4^n)*N), worst case of 7/9s we have 4 choices for each digit, and at each combination we need to concatenate the current to the output which takes N time
space: O(n) not including the output or the hashmap since that is constant, we care about the recursion tree height which is only ever N

class Solution:

• —def letterCombinations(self, digits):
• ——-if not digits:
• ———–return []
• ——-self.hashmap={“2”: [‘a’, ‘b’, ‘c’],
• —————“3”: [‘d’, ‘e’, ‘f’],
• —————“4”: [“g”, “h”, “i”],
• —————“5”: [“j”, “k”, “l”],
• —————“6”: [‘m’, ‘n’, ‘o’],
• —————“7”: [‘p’, ‘q’, ‘r’, ‘s’],
• —————“8”: [‘t’, ‘u’, ‘v’],
• —————“9”: [‘w’, ‘x’, ‘y’, ‘z’]}
• ——-self.output=[]
• ——-self.helper([], digits, 0)
• ——-return self.output
• —def helper(self, current, digits, index):
• ——-# could just do len(current)=len(digits) you idiot
• ——-if index[greater than]=len(digits):
• ———–self.output.append(““.join(current))
• ——-else:
• ———–num = digits[index]
• ———–for l in self.hashmap[num]:
• —————current.append(l)
• —————self.helper(current, digits, index+1)
• —————current.pop()

Question 8

Score of parentheses

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule:

”()” has score 1.
AB has score A + B, where A and B are balanced parentheses strings.
(A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: s = “()”
Output: 1
Example 2:

Input: s = “(())”
Output: 2
Example 3:

Input: s = “()()”
Output: 2
Example 4:

Input: s = “(()(()))”
Output: 6

Answer 8

brute force is a crazy divide and conquer, N^2 time and N space for the recursion stack

class Solution:

• —def brute(self, s: str) -[greater than] int:
• ——-return self.helper(0, len(s), s)
• —def helper(self, start, stop, s):
• ——-ans = bal = 0
• ——-for i in range(start, stop):
• ———–bal += 1 if s[i] == “(“ else -1
• ———–if bal == 0:
• —————if i - start == 1:
• ——————-ans += 1
• —————else:
• ——————-ans += 2 * self.helper(start + 1, i, s)
• —————start = i + 1
• ——-return ans

time: O(n)
space: O(n) bc of the stack, could get n sized

• —def whatIwouldGet(self, s: str) -[greater than] int:
• ——-stack = [0]
• ——-for x in s:
• ———–if x == “(“:
• —————stack.append(0)
• ———–else:
• —————value = stack.pop()
• —————stack[-1] += max(2 * value, 1)
• ——-return stack[-1]

time: O(n)
space: constant

• —def optimal(self, s: str) -[greater than] int:
• ——-ans = bal = 0
• ———–if x == “(“:
• —————bal += 1
• ———–else:
• —————bal -= 1
• —————if s[i-1] == “(“:
• ——————-ans += 1 [less than][less than] bal
• ——-return ans

Question 9

Valid palindrome

(string includes non-alpha-numeric characters, we need to ignore those)

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Answer 9

brute is to check if the reversed string is the same as original after we lowercase everything and remove the non-alphanumeric ones, with linear time and space

1. 2 pointers
2. while right >= left for main, then each pointer gets a while loop until the char.isalnum() returns True (is ABC 0-9) and right > left. it cannot be right >= left because if 1=1, then we subtract, right = 0 and left = 1, bad!

time: O(N) where N is s
space: cosntant

class Solution:

• —def isPalindrome(self, s: str) -[greater than] bool:
• ——-left, right = 0, len(s) - 1
• ——-while right [greater than]= left:
• ———–while right [greater than] left and not s[right].isalnum():
• —————right -=1
• ———–while right [greater than] left and not s[left].isalnum():
• —————left += 1
• ———–if s[left].lower() != s[right].lower():
• —————return False
• ———–left += 1
• ———–right -= 1
• ——-return True
• —def brute(self, s: str) -[greater than] bool:
• ——-lower = [x.lower() for x in s if x.isalnum()]
• ——-return list(lower) == lower[::-1]

Question 10

palindrome number

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

Answer 10

brute force is convert to string, see if s == s[::-1]

1. recreated the integer backward

time: Log base 10 (N), you can also say it is linear with respect to the number of 10’s that can be divided into it, but log10(N) probably sound smarter
space: constant

class Solution:

• —def isPalindrome(self, x: int) -[greater than] bool:
• ——-# need this check for anything that ends in 0, like 10 or 100
• ——-if x [less than] 0 or (x % 10 == 0 and x != 0):
• ———–return False
• ——-response = 0
• ——-final = x
• ——-while final [greater than] response:
• ———–response = response * 10 + x % 10
• ———–x //= 10
• ——-return final == response
• —def brute(self, x):
• ——-if x [less than] 0:
• ———–return False
• ——-s = str(x)
• ——-return s == s[::-1]

Question 11

Implement strStr():

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Example 1:

Input: haystack = “hello”, needle = “ll”
Output: 2
Example 2:

Input: haystack = “aaaaa”, needle = “bba”
Output: -1

Answer 11

brute force is to do O(n * (m - n)) where m and n are haystack/needle. This makes sure that you are never going out of index of the haystack. hay = 5, needle = 3, 5 - 3 = 2, but that means we only get 0 and 1 indexes, if it is aabcd and bcd, then we miss it, so we add 1 (standard index subtraction to make sure we don’t lose an index)

https://www.youtube.com/watch?v=GTJr8OvyEVQ

time: O(n * (m - n))
space: constant

• —def brute(self, haystack, needle):
• ——-for i in range(len(haystack) - len(needle) + 1):
• ———–if haystack[i: i + len(needle)] == needle:
• —————return i
• ——-return -1

https: //www.youtube.com/watch?v=GTJr8OvyEVQ
1. KMP, memorize it!
2. make sure to check edge cases, bc KMP does not check if they are none and such

time: O(haystack + needle). KMP requires us to make the longest proper suffix (LPS) array which is needle, then the search takes haystack time
space: O(needle) for the LPS array

class Solution:

• —def strStr(self, haystack: str, needle: str) -> int:
• ——-if not needle:
• ———–return 0
• ——-if not haystack:
• ———–return -1
• ——-n = len(needle)
• ——-h = len(haystack)——–
• ——-kmp_arr = [0]*n——–
• ——-needle_pointer = hay_pointer = 0——–
• ——-self.make_kmp_helper(kmp_arr, needle)
• ——-while hay_pointer < h:
• ———–if haystack[hay_pointer] == needle[needle_pointer]:
• —————needle_pointer += 1
• —————hay_pointer += 1
• ———–if needle_pointer == n:
• —————return hay_pointer - needle_pointer
• ———–# we increement np and hp on success, checking to make sure we do not double dip
• ———–if hay_pointer < h and haystack[hay_pointer] != needle[needle_pointer]:
• —————if needle_pointer != 0:
• ——————-needle_pointer = kmp_arr[needle_pointer - 1]
• —————else: #np is 0, start over
• ——————-hay_pointer += 1
• ——-return -1
• —def make_kmp_helper(self, arr, needle):
• ——-n = len(needle)
• ——-start, i = 0, 1
• ——-while i < n:
• ———–if needle[start] == needle[i]:
• —————start += 1
• —————arr[i] = start
• —————i += 1
• ———–else:
• —————if start != 0:
• ——————-start = arr[start - 1]
• —————else:
• ——————-arr[i] = start
• ——————-i += 1

Question 12

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:

Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”

Answer 12

1. vertical search is intuitive once you realize you can compare it against any arbitrary string, the first string being the easiest
2. on a failure during the loop we are finished so return, worst case when every word is the same we need a regular return

time: O(S ) where S is the total length of characters, you could also say O(S * L) where S is the length of the string list and L is the length of the longest string,
space: constant

class Solution:

• —def vertical_search(self, strs):
• ——-prefix = []
• ——-first = strs[0]
• ——-for i in range(len(first)):
• ———–for j in range(1, len(strs)):
• —————if i >= len(strs[j]) or first[i] != strs[j][i]:
• ——————-return ““.join(prefix)
• ———–prefix.append(first[i])
• ——-return ““.join(prefix)

1. when you find and it is not equal to 0, we slice the string and try again until we find Y in X at index 0 X.find(Y), this will tell us they have an equivalent prefix
2. Once we the longest prefix for X and Y, X and W can only have a smaller or equal one

time: O(S ) where S is the total length of characters, you could also say O(S * L) where S is the length of the string list and L is the length of the longest string,
space: constant

• —def horizontal_search(self, strs):
• ——-prefix = strs[0]
• ——-for j in range(1, len(strs)):
• ———–while strs[j].find(prefix) != 0:
• —————prefix = prefix[:-1]
• —————if not prefix:
• ——————-return “”
• ——-return prefix

Question 13

reverse a string

Answer 13

time: O(N), N/2 actually
space: constant, recursive is N/2

class Solution:

• —def recursive(self, s):
• ——-self.helper(0, len(s) -1 , s)
• —def helper(self, left, right, s):
• ——-if right > left:
• ———–s[left], s[right] = s[right], s[left]
• ———–self.helper(left + 1, right - 1, s)
• —def iterative(self, s):
• ——-left, right = 0, len(s) - 1
• ——-while right > left:
• ———–s[left], s[right] = s[right], s[left]
• ———–left += 1
• ———–right -=1
• —def slicing(self, s):
• ——-‘’’
• ——-start, stop, step. you could do s[len(s):-1]
• ——-‘’’
• ——-return s[::-1]

Question 14

reverse words in string

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = “the sky is blue”
Output: “blue is sky the”
Example 2:

Input: s = “ hello world “
Output: “world hello”
Explanation: Your reversed string should not contain leading or trailing spaces.

Answer 14

brute is to use factory methods, linear time and space

from collections import deque
class Solution:
----def factory(self, s):
--------return " ".join(reversed(s.split()))
--------'''
--------s ="b".join("ac") = abc
--------s ="b".join("a") = a
--------print(s)
--------'''

1. state machine, in word vs out of word
2. add spaces dynamically to response so we don’t need to do it later
3. after loop check if we are in the word, if so perform same action as above

time: O(N), where N is the size of s
space: O(N)

• —def optimized_linear_solution(self, s):
• ——-if not s:
• ———–return “”
• ——-response = deque()
• ——-start = 0
• ——-in_word = False
• ——-for i in range(len(s)):
• ———–if s[i] != “ “:
• —————if not in_word:
• ——————-start = i
• ——————-in_word = True
• ———–elif in_word:
• —————response.appendleft(s[start:i])
• —————in_word = False
• ——-if in_word:
• ———–response.appendleft(s[start:])
• ——-return “ “.join(response)

I got this my first try! worked and everything, but not optimized bc we add spaces after the fact instead of during

• —def linear_not_optimized(self, s):
• ——-if not s:
• ———–return “”
• ——-response = deque()
• ——-start = 0
• ——-in_word = False
• ——-for i in range(len(s)):
• ———–if s[i] != “ “:
• —————if not in_word:
• ——————-start = i
• ——————-in_word = True
• ———–elif in_word:
• —————response.appendleft(s[start:i])
• —————in_word = False
• ——-if in_word:
• ———–response.appendleft(s[start:])
• ——-response2 = []
• ——-for j in range(len(response)):
• ———–if j == len(response) - 1:
• —————response2.append(response[j])
• ———–else:
• —————response2.append(response[j] + “ “)
• ——-return ““.join(response2)

Question 15

reverse words in a string 3

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: s = “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”

Answer 15

time/space are linear. the iteration takes N time, the reverse will add N time as well, then appending to the response list is N time.

from collections import deque
class Solution:
----def factory_methods(self, s: str) -> str:        
--------return " ".join([w[::-1] for w in s.split()])

• —def reverseWords(self, s: str) -> str:
• ——-self.response = []
• ——-self.s = s
• ——-start = stop = 0
• ——-for i in range(len(s)):
• ———–if s[i] == “ “:
• —————self.reverse(start, i)
• —————start = i + 1
• ——-self.reverse(start, len(s))
• ——-return “ “.join(self.response)
• —def reverse(self, start, end):
• ——-word = deque()
• ——-for i in self.s[start:end]:
• ———–word.appendleft(i)
• ——-self.response.append(““.join(word))

Question 16

valid anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example 1:

Input: s = “anagram”, t = “nagaram”
Output: true

Answer 16

1. check if they are the same length
2. use defaultdict, each time one word has a char, add that to the default dict, when the second word sees it, subtract it
3. at the end check to make sure all values in the map are 0, if they are not we failed at some point and return false
4. we have to check if it is 0 bc one adds and one subtracts

time: O(n), we go through both lists once bc they need to be the same size
space: O(26), the hashmap can only have 26 characters so it is constant

from collections import defaultdict
class Solution:
----def isAnagram(self, s: str, t: str) -> bool:
--------if len(s) != len(t):
------------return False
--------
--------map = defaultdict(int)
--------# for x, y in zip(s, t):
------------# map[x] += 1
------------# map[y] -= 1
------------
--------for i in range(len(s)):
------------map[s[i]] += 1
------------map[t[i]] -= 1
--------
--------for key, value in map.items():
------------if value != 0:
----------------return False
------------
--------return True

• —def array_solution(self, s: str, t: str) -> bool:
• ——-if len(s) != len(t):
• ———–return False
• ——-counter = [0] * 26
• ——-for i in range(len(s)):
• ———–counter[ord(s[i]) - ord(‘a’)] += 1
• ———–counter[ord(t[i]) - ord(‘a’)] -= 1
• ——-for value in counter:
• ———–if value != 0:
• —————return False
• ——-return True

Question 17

can place flowers

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0’s and 1’s, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

Answer 17

1. greedy solution
2. at each index, check if it is a valid spot, if it is modify the starting array and continue
3. if you cannot modify the starting array, you will need to make a map and reference that when you make changes

time: O(n)
space: constant, if we cannot modify the input array then it would be linar

class Solution:

• —def cleaner(self, flowerbed, n):
• ——-if n == 0:
• ———–return True
• ——-for i in range(len(flowerbed)):
• ———–if flowerbed[i] == 0 and (i == 0 or flowerbed[i - 1] == 0) and (i == len(flowerbed) - 1 or flowerbed[i + 1] == 0):
• —————flowerbed[i] = 1
• —————n -= 1
• —————if n == 0:
• ——————-return True
• ——-return False
• —def canPlaceFlowers(self, flowerbed, n):
• ——-if n == 0:
• ———–return True
• ——-for i in range(len(flowerbed)):
• ———–if flowerbed[i] != 1:
• —————back = False
• —————forward = False
• —————if i - 1 >= 0:
• ——————-if flowerbed[i - 1] != 1:
• ———————–back = True
• —————else:
• ——————-back = True
• —————if i + 1 < len(flowerbed):
• ——————-if flowerbed[i + 1] != 1:
• ———————–forward = True
• —————else:
• ——————-forward = True
• —————if forward and back:
• ——————-n -= 1
• ——————-flowerbed[i] = 1
• —————if n == 0:
• ——————-return True
• ——-return False

Question 18

93. Restore IP Addresses

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses, but “0.011.255.245”, “192.168.1.312” and “192.168@1.1” are invalid IP addresses.
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Example 1:

Input: s = “25525511135”
Output: [“255.255.11.135”,”255.255.111.35”]
Example 2:

Input: s = “0000”
Output: [“0.0.0.0”]

Answer 18

1. backtracking!
2. base case is if start index == len(s) and there are 4 items in the cur array
3. loop over i, range(start, min(start + 3, len(s)) bc that accounts for if you get x.x.x.1 instead of going out of range you get just the end!
4. 0.0.0.0 is valid, if the first index is 0 that is okay as long as you don’t do 02.05, so check if start == 0 and i > start, if so that is a bad case and break the loop

time: O(3^n) where n is the valid number of octets. in this example, n = 4 so it is constant at 81
space: O(n) where n is the number of valid octets due to backtracking, in this case 4. for response array, it is O(1) bc we can calculate how many ip’s at each string length.

class Solution:

• —def restoreIpAddresses(self, s):
• ——-self.response = []
• ——-self.s = s
• ——-self.back_track(0, [])
• ——-return self.response
• —def back_track(self, start, cur):
• ——-if len(cur) == 4:
• ———–if start == len(self.s):
• —————self.response.append(“.”.join(cur))
• ———–return
• ——-for i in range(start, min(start + 3, len(self.s))):
• ———–# this is for the 0.0.0.0 cases where we have 0s, but we don’t want 02.01, checked by i > start
• ———–if self.s[start] == “0” and i > start:
• —————break
• ———–if int(self.s[start: i + 1]) <= 255:
• —————# cur.append(self.s[start: i + 1])
• —————# self.back_track(i + 1, cur)
• —————# cur.pop()
• —————# if you do backtracking on lists, you list + list(item) which concatenates them. It acts as making a new variable
• —————self.back_track(i + 1, cur + [self.s[start:i + 1]])