- use hash to store `num:index` while traversing
- check `diff = target - num` exist in hash. i.e `hash[diff] >= 0`
- if not store num:index in hash (not diff). i.e `hash[num] = index`
- use TWO pointers.
- use set to keep track of all chars while traversing
- only move RIGHT until we found char in set.
- remove left char, move left pointer and repeat
- use TWO pointers. But they move OUTWARD from start. <-- left right --->
- Handle ODD and EVEN condition seperate
- Use forloop for traversing the chars one at a time for both ODD and EVEN while loops
- ODD: assing left = index, right = index and check palindrome inside while loop
- EVEN : assing left = index, right index+1 and check palindrome inside while loop
- use TWO pointers. start left at the begining and right at the end
- calculate area everytime inside while loop and update to maxArea only if it's more
- Area = length of shorter vertical line * distance between lines
- i.e `let area = min(height[left], height[right]) * (right - left);`
- move left or right if one of them is less than or equal to other one.
- break this problem into a loop problem plus two sum sorted array problem
- Result array shouldn't have same element in same position in the result set ( still confused )
- we sort the array so we can array TWO SUM sorted array method
- if we find same elements in consecutive postion, we skip both in outer loop & in TWO SUM logic
- i.e skip in outerloop: `if(iThElement === nums[i-1]) { continue }`
- i.e skip inside TWO SUM: `while(leftElement === nums[left-1]) { left ++ }`
- TWO pointers slow and fast start at dummy
- use DUMMY (dummy = new ListNode() ) and dummy.next = head ( helps in solving two elements )
- move fast, n+1 times so our slow will be one step behind the nth element
- second while loop should just check fast if we have done n+1 times fast. i.e `while(fast){...}`
- return dummy.next instead of head so we can solve problems with just one element
- use hashmap for storing brances where key is closed brace and value is open brace.
- i.e `let hash = { ')':'(', ']':'[', '}','{' }`
- use stack where we will only add open brances
- if we are processing closing brance then check corresponding open brance from hash and
last element in stack are equal. If so we pop item from stack.
- if stack is empty at the end then we had valid parentheses stack.length === 0 as answer.
- Note: if we get just ']' as input then this fails so we need to have else check
which return false when we are processing closing brace and stack/empty
last item doesnt match
- Add else conditon to return false when "dict[char] === stack[stack.length-1]" fails and
we couldn't pop.
- use dummy and we will compare list1 and list2, then add pointer to dummy
- also have another pointer head/root pointing to dummy. so we can return head.next
- after every comparision we need to move either list1 or list2 and dummy.
- do last check to make sure we didn't leave anything in either list.
- i.e `return dummy.next = list1 ? list1 : list2`
- instead of two sorted linkedlist we have K number of linkedList
- Approach 1 (Not Optimal): time: O(N*K) where N is size of linkedList, K is number of linkedList and space: O(1)
-- we merge two linkedList at a time in order
-- create mergeTwoSorted function. which returns head for merged two list
-- for first time, apply `mergeTwoSorted` on `lists[0]` and `lists[1]`.
-- use for loop starting at `i=2` and use the head from above and repeat `mergeTwoSorted(head, lists[i])`
-- do `if(!l1 && !l2) return dummy.next;` check in mergeTwoSorted for input like `[[]]`
- Approach 2: time: O(NlogK) and space: O(1)
-- we merge two linkedList at a time but in pairs. Then we run merge again on those results.
-- will make use of mergeTwoSorted function which returns head for merged two lists
-- we will call mergeTwoSorted until we are left with one linkedList in lists
-- i.e `while(lists.length > 1) { .... }`
-- we make use of tempMergedLists=[] to hold merged lists for every for loop, then assing
tempMergedLists to lists. i.e 'lists = tempMergedLists` at the end of for loop.
-- we call mergeTwoSorted function with pairs i.e `for(let i=0; i<lists.length; i=i+2)`
- Naive way is loopig and finding in O(N) time. But we need to do in O(logN)
- we can use Binary Search concept on sorted array and use if conditions to direct which way
the search needs to go as we dont have PERFECT sorted array
- write down BS for sorted array and call from parent like `return bs(nums, target, 0, nums.length-1)`
- if for some reason we find our target value LOWER than sorted array's left most value,
we call binary search on right side of the MID
- if for some reason we find our target value GREATER than sorted array's right most value,
we call binary search on left side of the MID
- also have normal binary search calling when target is less than mid, we go binary search
on left side and if target is more than mid then we go binary search on right side
Ans: Diagram Solution
- Hence we cannot have same combination of elements in diff permutations
the problem cannot be solved using two loops
- treat this as tree probelm, we can do BACKTRACKING to alter the combination
by adding and removing via DFS.
- Hence each element combination can be used manytimes once until we find TARGET or SUM exceeds target.
- At root of the tree we will have two choice, one with including the i'th
element in combination and another without including i'th element.
- we keep adding other elements to these until we reach base case.
Ans: Diagram Solution
- treat this as problem (outer matrix) and sub problem (inner matrix )
- we move value from top left -> top right -> bottom right --> bottom left and
lastly top left.
- so we need left,right boundry for column. top,bottom for row.
- instead of moving clockwise ( as mentioned in second point ). we move
counter clock after saving TOP LEFT value in temp. Which will save having
to hold other values in temp.
- need for loop which runs uptp (r-l) range. This will help in moving pointers
from left to right
- Aproach 1: By Sorting Each String (Not Optimal: Time O(NMlogM))
-- anagram strings will match when they are sorted. i.e eat & tea will be aet
-- we go through each string, split them by space, sort them, join them to make a key
-- use sorted string as key and actual string as values.
-- loop though the hash to build resulting array
- Aproach 1: By Counting Characters from Each String (Time O(NM))
-- anagram strings will match when they are sorted. i.e eat & tea will be aet
-- go through each string and it's char's then build key using char's ASCII
-- i.e `let count = new Array(26).fill(0)`
and count[`${char}`.charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
-- store str with respect to 'count' key in hash
-- loop through hash to get resulting array
- Appraoch 1: ( not optimal ) we could do using two forloop with
max value holder and sum. O(n^2)
- Appraoch 2: O(N) with same max and sum
-- will have one loop, but sum and max will have first element value to start with
-- for loop will run from i=1, where sum will ONLY get updated when
`sum = Math.max(sum, sum+nums[i])`. this prevents it going less than current sum.
-- max will be `max = Math.max(max, sum)`
- we need 4 limiters
- rowStart = 0, rowEnd = matrix.length-1, colStart=0, colEnd=matrix[0].length-1;
- we traverse in while loop as long as `while(rowStart <= rowEnd && colStart <= colEnd ){.}`
- will have 4 for loops inside to control the directions
- imp: we need boundry check `if(rowStart > rowEnd || colStart > colEnd) break;` in place
after first two for loops
- appraoch 1: Dynamic Programming
-- brutforce will result in O(n^n) time but adding memo will reduce it to O(n^2)
-- brutforce is DP problem where main function will call helper function with index 0
and input array. i.e `return jumpHelper(0, nums)`
-- use `Map` instead of array for memo
- appraoch 2: Greedy ( going from back to first will result in time: O(n) )
-- instead of going from start to destination (last). We can go from back
-- every time we decrement `i` we check if we can reach the destination from given index
-- i.e `if(i + maxJumpLength >= destination) { destination = i }` then we move destination
closer
-- check if our destination is at 0th index, if yes we can reach destination from start
- If it is not sorted we will need to sort (O(logn)) AND total complexity is O(nlogn)
- Add first element to result and loop from second element
- compare if new interating elements first item is LESS than last result elements second
item.
- if yes then we merge. But we need to consider min of first position elements and maximum
of second position elements i.e `result[result.length-1][1] = Math.max(rSecond, newSecond);`
- if not we add iterating element to result, and move on
i.e `result.push([newFirst, newSecond])`
- given intervals is already sorted so time:O(n)
- while adding newInterval to sorted intervals we need to consider 3 things
- # handle newInterval if it needs to be added at first and return updated result array
-- i.e `return [...result, ...intervals.slice(i)];`
- # handle adding interval form intervals to result if newInterval comes after
- # handle merging newInterval until newInterval[1] is greater than interval[i][1]
-- i.e we can keep updating
`newInterval = = [Math.min(first, newFirst), Math.max(second, newSecond)]`
- # handle adding newInterval at the end of intervals if newInterval[1] is greater than tail
- Second Optimal: Time: O(m*n) and Space: O(m+n) using two 1-D array (rowArray, colArray) to hold
the values corresponding to matrix[row][col].
-- first time for loop to update rowArray and colArray based on matrix cell values
-- second time for loop to update the matrix based on rowArray and colArray matching cell values
- Best Optimal : Time: O(n*m) and Space: O(1) using one variable to hold matrix[0][0] value and
using first row and column as reference to update the rest of the matrix.
-- instead of using rowArray and colArray we use matrix's first row and col as reference
-- we will hold rowZero = false as default which will reflect matrix[0][0] value
-- we will do three update process
-- first to update the row/col values based on first row and first col values
-- second to update the row's first column values based on matrix[0][0] (i.e first cell)
-- third to update the first column's first rows values if rowZero is true
- Time: O(S+T) Space: O(S+T)
- Sliding window
- Need two hash maps
- need to shrink left after finding the substring containing second strings all char
- Time: O(n+m * 4^n) where n is chars of search word. Space: O(m*n)
- Apply DFS with Backtracking
- BackTracking : Second example will fail if we dont delete visited entry at the end
of completing dfs.
- WordIndex: we need wordIndex in DFS which we will use it to check if we completed
the complete WORD comparision.
-- i.e if(startIndex === word.length-1) return true.
- Compare Each character with Word: we need to check if traversing in matrix cell value matches with word chars by our StartIndex. i.e `if(matrix[row][col] !== word.charAt(startIndex))
return false`
- Tree combination can be used which will give 2^n time complexity as we have two choices to make every time
-- 1st choice using just 1 char and second choice to use 2 char as we have valid code from 1 - 26
- with dfs and memo we can solve this in O(n) time and space
- we will call dfs with 0 index and initalize the MEMO with default `s.length : 1` as we need to return 1 if empty
- if we find s starts with 0 then its invalid ( number ranges from 1-16 )
- we will add dfs recursively only if second char pair satify range from 10-26
- Time: O(N) and Space:O(N)
- In valid BST root value will be greater than left children and less than right children
- If we are doing recursion, then have left and right min max value assigned like left = -Infinity and right = Infinity
- validate if root.val will satisfy left < root.val < right
- call left children and right children
like `return valid(root.left, left, root.val) && valid(root.right, root.val, right)'
- time:O(n) and sapce:O(logN) in best and O(n) in worst
- dfs and traversing both tree's together and comparing
- dfs should compare left and right side with &&.
-- `if(p && q && p.val === q.val) return dfs(p.left, q.left) && dfs(p.right, q.right)`
- time:O(n) and sapce:O(n)
- Iterative method using bfs level order
- use queue.shift() to pop first element and queue.push() to add element
- time:O(n) and sapce:O(n)
- Iterative method using bfs level order
- use queue.shift() to pop first element and queue.push() to add left and right element
- keep counter and increase it at the end of for loop <--- *** IMP ***
- preorder is ROOT, LEFT, RIGHT
- inorder is LEFT, ROOT, RIGHT
- first element of preorder is always ROOT. So we can creare new tree node from
this (i.e node = preorder.shift() )
- finding index of node in inorder will help finding right and left part
of new tree. (i.e pivot = inorder.indexOf(node))
- root.left = buildTree(preorder, inorder(0, privot) and root.right = buildTre (preorder, inorder(pivot+1)
- Bruteforce: Time: O(n^2) can be done with two for loops with i=0, j=i+1;
- Optimized: Time: O(n) by keeping `minPrice` and `profit` as global variable.
-- Goal here is to find the min price first and once we no longer find it we calculate profit.
- find minPrice by `if(price < minPrice) { minPrice = price; continue }`. we continue to next.
- if we find price > minPrice we calculate profit.
-- i.e `if(price - minPrice > profit) { profit = price - minPrice }`
- Time: O(N) Space:(H) where H is the height of the tree
- Will apply DFS ( inline function so we can reference local variable )
- Will have global max which will get updated by DFS. i.e `let maxSum = -Infinity;`
- DFS base will check for root null and return 0;
- we calculate left by calling DFS with root.left i.e `left = DFS(root.left)`;
- we calculate right by calling DFS with root.right i.e `right = DFS(root.right)`;
- we will need max of these compared to '0' so we always have +ve value. <-- *** IMP ***
-- example: root = [2,-1,-2] and we should only consider 2 and ignore rest
- we update max by comparing max and combination of leftMax + root.val + rightMax
- ew return max between leftMax + root.val or rightMax + root.val
- Time: O(N) even with regex (used by string replace as well), Space:O(1)
- use TWO POINTER with left = 0 and right = s.length-1. Move inward.
- we will split, convert to lower and remove special char either using regex or charCodeAt() function.
- With regex => `s = s.replace(/[^A-Za-z0-9]/g, '').toLowerCase()`
- Without regex : need to build helper and use `var input_char = input.charCodeAt(0);` then compare
for `if (input_char >= 97 && input_char <= 122 || input_char >= 48 && input_char <= 57){ return true }`
Ans: Diagram Solution
- Not Optilmal : Time:O(nlogn) and Space:O(1)
- sort and then have curLength, maxLength =1 and find maxLength by comparing
- Optimal : Time:O(n) and Space:O(n)
- Use Set to store nums ( removes duplicates )
- Using set we can look up if the given number in set has previous number. Example: if '1' doesnt
have previous number we get the clue it is the starting.
If not then it is the start of the range we calculate. If the numer has left or previous in
the Set then we can assume it is not the start
- we will apply dfs. time: O(m+n) and space: O(N) where N is depth os stack
- use Map instead of Set so we can keep track of node -> cloneNode.
-- i.e visited.set(node, clone) and we can check `visited.has(node) then return visited.get(node)`
which will return pointer to respective clone rather than original node.
- iterative over node's children and build cloneChild and push it to clone.childrens array.
- we can solve this with recursion and memoization which will result in O(n^3) time
- will need to use TWO POINTER in recursion
- use Map for memo instead of array for Time Limit exceed exception
- call helper(s, wordDict, 0, memo) and use forloop/while inside helper for finding substring with
another pointer end = start + 1 ( to start with ).
- OR we can also solve this in DP with memoization will result in O(n^3) as well
- we can solve this with recursion and memoization which will result in O(n^3) time
- will need to use TWO POINTER in recursion
- use Map for memo instead of array for Time Limit exceed exception
- call helper(s, wordDict, 0, memo) and use forloop/while inside helper for finding substring with
another pointer end = start + 1 ( to start with ).
- OR we can also solve this in DP with memoization will result in O(n^3) as well
- we need to do this in three steps. Find Mid, Reverse, Merge.
- Find Mid: slow = node.next where fast = node.next.next
- Reverse: future = cur.next; cur.next = prev; cur = future; prev = cur; and we return pre.
- Merge: head = l1; tmp = l1.next; l1.next = l2; l1 = tmp. Similary tmp = l2.next; l2.next = l1; l2 = tmp.
- Brute Force: Time: O(n^2) with two loops
- Kadanes: Time: O(n)
- Have three variable. result points to first element so we return first element as default. curMin and curMax
- i.e result = nums[0], curMin = 1, curMax = 1
- Loop through each element and update the curMin, curMax, and result. finally return result.
- curMax = Math.max(num, num*curMax, num*curMin)
- curMin = Math.min(num, num*curMax, num*curMin)
- result = Math.max(result, curMax)
- Time: O(logN) Space: O(1)
- Hence this needs to be solved in O(logn). We will use binary search
- Binary search is done on sorted array but we have sorted with pivot. So will need small
alteration to nomal BS.
- we will have left = 0; right = nums.length-1 and result = nums[0].
- with in while check if the given array is already sorted then return left most value comapred
to result (i.e nums[0])
- if we didnt do early return then find mid, check if mid is smallest compare to result.
- check if left part of mid is already sorted, then move left pointer to mid+1 else right
pointers to mid-1
- Time: O(N) and Space:O(N)
- we will need to do bit shifting and masking i.e mask = 1
- we will need to calculate for 32 bit.
-- i.e `for(let i=0; i<32; i++)`
- if we add 1 to the given bits we will get 0 if bits has 1 or 0 if bits has 0.
-- `if((mask & n) !== 0){ count ++ }`
- if the result is 0, then we can say bits has 1 and we increase the count.
- then we need to mask or shit i.e mask <<= 1;
- Time: O(N) and Space:O(N)
- can we solved with recursion & memoization which will have
- can also be solved using DP with time:O(N) and Space:O(1)
- in DP,
-- we initialize rob1 and rob2 be ZERO. will be used as pre-steps for given nums.
-- i.e // [rob1, rob2, n, n+1, n+2, ...]
-- while traversing the nums array. we will need to calculate max gain between two options
-- temp = Math.max(rob1+nums[n], rob2);
-- move the pointers rob1 and rob2 i.e rob1 = rob2; rob2 = temp
- Time: O(M*N) and Space: O(M*N)
- DFS heper will be called with grid,row, col, visited.
- we need to call on each sell so it will be two for loops to call DFS.
- we can precheck before calling DFS and if it returns true we incrment count
- DFS will check row/col our of bound check, visited check, water check and returns false for all
- DFS on all 4 ways and finally return true
- have dummy point to null
- use while loop i.e while(head)
- temp = head.next; head.next = dummy; dummy = head; head = temp;
- return dummy
- Time: O(N+M) where N is number of courses and M is number of dependencies. Space: O(N+M)
- Will do DFS recursiuon on the adjList
- Will initialize the adjList with courses by looping over numCourses.
- will add [course, pre] = pair from preReq's and add course dependecies in adjList like `adjList[course].push(pre)`
- will call DFS for all the courses from numCourses
- dfs should have visited check, adjList[course].length === 0 check to return true,
looping all pre from preReqs using DFS
- we will only do early false return <-- ***IMP***
- end of all DFS we will need to remove course from visited set and update course in
adjList to be empty. i.e `visited.delete(course); adjList[course] = [];` <-- ***IMP***
Ans: Diagram Solution
- define TrieNode with children (empty hashmap) and endOfWord boolean defaulted to false
- define Trie with constructor this.root = new TrieNode();
- define insert method which takes word. we check for each char in word for node.children
if char doesnt exist in children then we create new TrieNode for that char. if exists then
we move node to char Trie. i.e (node = node.children[char]);
- define search method and do as abvove but return false if char doesnt match. if matched
keep moving pointer. At the end return `node.endOfWord;`
- define startsWith and follow the same as search but at the end we simply return "TRUE"
and no need to check if we reached end of the word.
- Time: O(M) for well defined words without '..' dots. M is key length & N is number of words. Space: O(1)
- Time: O(N * 2^M) for '..words' where M represnts '...'. Space:O(M) for undefined words from recursion.
- Same Trie implementation as above except search will now need to handle basic search when word has all
alphabets like 'abc' and also when wild card is used like '.ab'.
- Define TrieNode, Implement Trie class with addWord function (same as insert trie method)
- Define Search method which will pass info to DFS and returns only when DFS returns true.
- DFS will take word, node, startIndex and will return node.endOfWord at the end.
- Inside DFS, will loop though char of word and break the problem into handline char with '.' and without
-- if char is '.' then we extract all values from node.children ( so we can find try matching on every child node ).
then call DFS recursively with same word, i+1, child. i.e DFS(word, i+1, child)
-- if char is not '.' then will do normal search workflow
- Best Appraoch: Use Set which will result in O(n) time and O(n) sapce
- Second Best Approach: Sorting and then checking with TWO pointers. time:O(nlogn) and space:O(1)
- Time:O(n) and Space:O(n)
- Can be done recursively or iterative appraoch
- In recursive,
root.left = invert(root.right); root.right = invert(root.left)
- In iteravtive,
let node = stack.pop(); let temp = node.left; node.left = node.right; node.right = temp and add node.left and node.right
to stack.
- Best Appraoch:
- Time:O(n) and Space:O(logn) in average case and O(n) in worst
- Do in oder processing in iterative manner
- return k-1 index from array built from in order processing
- Second Best Approach:
- Time:O(n) and Space:O(n) from recursion
- Do in oder processing in recursion
- return k-1 index from array built from in order processing
- LCA / getLCA / get common parent
- We will need to do recursion on left or right node as it is balanced tree
- base conditions: if root is null we return root
- we check if p.val and q.val is less than root.val then we do recursion on left
-- return LCA(root.left, p , q)
- we check if p.val and q.val is greater than root.val then we do recursion on right
-- return LCA(root.right, p, q)
- if neither then we simply return root as it is BST and it must be balanced already
- LCA / getLCA / get common parent
- We will need to do recursion on left and right node
- base conditions: if root is null we return root
- base conditions: if ONE of given node is equal to root then root must be the parent
-- if(root === p || root === q) return root
- recursion: run LCA on left and right node of root.
-- left = LCA(root.left, p, q); right = LCA(root.right, p, q);
- if we get value from both left and right we return root (if(left && right) return root)
- if one of then is true (i.e both p & q belongs to either left or right ) then we return that side.
-- return left ? left : right
- Best Appraoch:
- Time:O(n) and Space:O(1) if we exclude ans array
- calculate left product by starting prodArray[0] = 1.
- prodArray[i] = prodArray[i-1] * nums[i-1] will fill the product of rest of the cell
- Use rightProductSum = 1 as product holder of right
- loop though the prodArray from right to left by doing so we will calulate produt and
rightProductSum
-- i.e productArray[i] = rightProductArray * productArray[i1]
-- update rightProdArray as rightProductSum = rightProductSum * nums[i];
- Second Best Approach:
- Time:O(n) and Space:O(n)
- calculate leftProductArray from left to right where leftProductArray[0] = 1;
-- i.e leftProductArray[i] = leftProductArray[i-1] * nums[i-1];
- calculate rightProductarray from right to left where rightProductArray[nums.length-1] = 1;
-- i.e rightProductarray[i] = rightProductarray[i+1] * nums[i+1];
- finally we will have one more array which does product of these two
- Best Appraoch:
- Time:O(n) and Space:O(1) if we exclude ans array
- calculate left product by starting prodArray[0] = 1.
- prodArray[i] = prodArray[i-1] * nums[i-1] will fill the product of rest of the cell
- Use rightProductSum = 1 as product holder of right
- loop though the prodArray from right to left by doing so we will calulate produt and
rightProductSum
-- i.e productArray[i] = rightProductArray * productArray[i1]
-- update rightProdArray as rightProductSum = rightProductSum * nums[i];
- Second Best Approach:
- Not the Best Appraoch:
- Time:O(nlogn) and Space:O(1) if we sort them
- Best Appraoch:
- Time: O(N) and Space: O(N) using hash map.
- will do three for loops, one for counting s char in one map, in second loop we
decrement char from the map.
- in last loop we check if count is 0, otherwise throw an error
- Bruteforce:
- Time:O(n^2) Space:O(1)
- Using two forloops to find the combinations
- Best Appraoch:
- Time: O(nlogn) Space:O(1)
- sort them by start value
- if curStart time less than previous endTime then we return FALSE
- Best Appraoch:
- Time: O(nlogn) Space:O(n)
- Seperate start and end values to diff array and sort them.
- Do while loop with start,end = 0. Here we will have to handle two scenario
-- Non-Overlap: if(start < end) we increment room count
-- Overlap: if(start >= end) we decrement room count
- return max between count vs maxCount (which holds max value we found in count)
- Time: O(N+M) and Space:(N+M) where N is height
- DFS called with starting node i.e parent
- Need to build adjList
- In DFS, we need to only call DFS on child if `parent !== child`
- We need to check we traversed all the nodes. i.e `visited.size === n`
- Time: O(n) and Space: O(n)
- Using combination of Set and loop to find the missing number
- Confirm if the given number always starts from 0 and ranges from 0.
- If yes, then we can simply treat last number is nums.length + 1.
- will do for loop and check if we have missing number in Set until last num.
- Time: O(n) and Space: O(H) where n is number of chars in all words
- DFS with Postorder ( postorder will help in solving DAG issues with DFS)
- AdjList:
-- initialize adjList with chars from all words
-- we map one char by taking from wordOne and wordTwo as long as they are not same.
and we break instead of checking rest ( as chars after doesn't help us with order )
- Wrong input check:
-- we need to check if the given words are in lexical order as they say.
-- i.e small length word should be at first as long as they have same prefix
- DFS:
-- call DFS with all elements in adjList ( to handle multiple disconnected graph)
-- will need to have hasCycle check and visited check to avoid checking
-- DFS will process in POSTORDER manner and pushes char to result array
-- we reverse and return result array
- Time: O(N) and Space:O(N)
- Need to consider handlign number and special chars.
- encode formula : length of the word + # + word => 5#Hello
- Decode: start with index = 0 and while loop until index < length of string
-- use tempIndex = index ( so we can update the index for next word )
-- Use another while loop to move "tempIndex" until char is not equal to #
-- Now process number comes before # and same it after parseInt.
-- Find word using substring, push it to result array
-- process next word so we update index = tempIndex + 1 + numSize
- Time: O(N) and Space:O(N)
- Need to consider handlign number and special chars.
- encode formula : length of the word + # + word => 5#Hello
- Decode: start with index = 0 and while loop until index < length of string
-- use tempIndex = index ( so we can update the index for next word )
-- Use another while loop to move "tempIndex" until char is not equal to #
-- Now process number comes before # and same it after parseInt.
-- Find word using substring, push it to result array
-- process next word so we update index = tempIndex + 1 + numSize
Ans: DFS Diagram Solution
- Time: O(N^2) and Space:O(N)
- Option 1: Can be done with DFS and memoization
- Option 2: Dynamic programming by dividing this into sub problem and recurrence
- DP:
-- We will initialize dp array of same size with 1 as default value. Default length
to reach these i'th value is 1.
-- we will use TWO forloops and starting at i=1. Everytime we will calculate max
length we could find by checking previous dp. i.e when we are at dp[3] we will calculate
dp[3] value by using combination of dp[0], dp[1], dp[2].
-- will return max value from the dp array
