[LeetCode] 161. One Edit Distance

 Problem : https://leetcode.com/problems/one-edit-distance/

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        
        def helper(i, j, edit):
            if i == len(s):
                return j + edit == len(t)
            
            if j == len(t):
                return i + edit == len(s)
            
            if s[i] == t[j]:
                return helper(i+1, j+1, edit)
            else:
                if edit == 0:
                    return False
                
                # delete / insert / replace
                return helper(i+1, j, edit - 1) or helper(i, j + 1, edit - 1) or helper(i+1, j+1, edit-1)
        
        return helper(0, 0, 1)

[LeetCode] 389. Find the Difference

 Problem : https://leetcode.com/problems/find-the-difference/

Use hash table to find the difference:

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        counterS = Counter(s)
        counterT = Counter(t)
        
        for k, v in counterT.items():
            if counterS[k] != v:
                return k

[LeetCode] 388. Longest Absolute File Path

 Problem : https://leetcode.com/problems/longest-absolute-file-path/

Use two pointers approach to parse directory / file name.

Use stack to maintain the paths to current files. We need to pop directory from stack is depth of current file is less than the directory on the top of the stack.

Time Complexity = O ( N ).   N = len(input).  As the code only visit each character in the input once.

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        if not input: return 0 
        
        result = 0
        
        # Stack<[fileName, depth]>
        stack = []
            
        left = right  = 0
        depth = 0
        
        while right < len(input):
            if input[right] == '\n' or right == len(input) - 1:
                # pop back to the depth of current file
                while stack and stack[-1][1] >= depth:
                    stack.pop()
                
                # find current file name
                file = input[left:right] if input[right] == '\n' else input[left:right+1]
                stack.append([file, depth])
                
                # calculate the full path to a file
                if '.' in input[left:right]:
                    paths = '/'.join([a for a, _ in stack])
                    result = max(result, len(paths))
                
                # calculate next depth
                right += 1
                left = right
                depth = 0
                
                while right < len(input) and input[right] == '\t':
                    depth += 1
                    right += 1
                
                left = right
            else:
                right += 1
        
        return result

[LeetCode] 387. First Unique Character in a String

 Problem : https://leetcode.com/problems/first-unique-character-in-a-string/

class Solution:
    def firstUniqChar(self, s: str) -> int:
        counter = Counter(s)
        
        for i, n in enumerate(s):
            if counter[n] == 1: return i
        
        return -1

[LeetCode] 386. Lexicographical Numbers

 Problem : https://leetcode.com/problems/lexicographical-numbers/

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        result = []
        
        def backtrack(x):
            if x <= n:
                result.append(x)
            
                for t in range(10):
                    if x * 10 + t <= n:
                        backtrack(x*10 + t)
                    else:
                        break
            
            return result

        result = []
        for x in range(1, 10):
            if x <= n:
                backtrack(x)
        
        return result

[LeetCode] 385. Mini Parser

 Problem : https://leetcode.com/problems/mini-parser/

Time Complexity = O (N ** 2)

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        if not s: return NestedInteger()
           
        if s[0] != '[': return NestedInteger(int(s))
        
        if len(s) <= 2: return NestedInteger()
        
        result = NestedInteger()
        
        left = 1
        lb = rb = 0
        
        for right in range(1, len(s)):
            if s[right] == '[':
                lb += 1
            elif s[right] == ']':
                rb += 1
                
            if (lb == rb and s[right] == ',') or right == len(s) - 1:
                result.add(self.deserialize(s[left:right]))
                left = right + 1
                
        return result

[LeetCode] 384. Shuffle an Array

Problem : https://leetcode.com/problems/shuffle-an-array/

class Solution:

    def __init__(self, nums: List[int]):
        self.nums = nums

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        return self.nums
        

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        
        shuffled = self.nums[:]
        N = len(shuffled)
        
        for i in range(N):
            j = random.randint(i, N-1)
            shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
            
        return shuffled


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

[LeetCode] 383. Ransom Note

Problem : https://leetcode.com/problems/ransom-note/

Time Complexity = O ( M + N  ).  M = len ( magazine ), N = len ( ransomNote )

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        counter = Counter(magazine)
        
        for r in ransomNote:
            if r not in counter or counter[r] <= 0:
                return False
            else:
                counter[r] -= 1
        
        return True

[LeetCode] 382. Linked List Random Node

 Problem : https://leetcode.com/problems/linked-list-random-node/

The naive way is calculating the length of the list first, then randomize the position in the list. But how to get the random node when it is expensive to get the list length. For example, assume the list is saved on remote server and the operation 'getNext' is very expensive. How to collect get the random node with minimal cost?

The answer is Reservoir sampling.

To make the problem more generically, let's say we need to sample k elements.

Suppose we have an element at the position of i ( i > k ), when we reach the element, the chance to select this element is  k / i.

Later on, we can select another element to replace the ith element.  For i+1 element, the change for it is not be selected is  1 - 1 / (i+1) = i / (i+1). 

So if ith element will eventually be selected, its chance is:

(the probability of ith element be selected ) * (  the probability of i+1th element not be selected to replace ith element) 

= (k / i ) *  (1 - 1 / (i+1)) 

= (k/i) * (i / i+1) 

= k / (i+1).    

def reservoirSample(S, R, K):
    """
    S : the items to sample
    R : the selected sample items
    K : number of the needed sample items
    """
	
    # fill the reservoir array
    for i in range(K):
        R[i] = S[i]
        
    # replace elements with gradually decreasing probability
    for i in range(K, len(S)):
        j = random.randint(0, i)
        if j <= k:
            R[j] = S[i]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode head;
    Random random = new Random();
    
    public Solution(ListNode head) {
        this.head = head;    
    }
    
    public int getRandom() {
        
        ListNode p = this.head;
        
        int result = p.val;
        int count = 1;
        p = p.next;
        
        while (p != null) {
            count += 1;
            
            if (random.nextInt(count) == 0) {
                result = p.val;
            }
            p = p.next;
        }
        
        return result;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

Edited on 1/7/2022. Replaced with reservoir sample solution.

[LeetCode] 381. Insert Delete GetRandom O(1) - Duplicates allowed

 Problem: https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

Similar to the problem # 380, to get O(1) time complexity for deleting operation, we need to save the index of each value in the value list.  Because it allows duplicated value be inserted and deleting item from bidirectional linked list is O(1). we can manage nodes with same value in a bidirectional linked list. Then the hash table saves the index of the last item of one value's bidirectional linked list. 

class Node:
    def __init__(self, val, pre, nxt):
        self.val = val
        self.pre = pre
        self.nxt = nxt
        
        
class RandomizedCollection:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        # nodes with same value are linked as a bidirectional linked list
        # dict[K] save the index of the last node of number K's linked list 
        self.dict = defaultdict(lambda: -1)
        
        # save all values
        self.list = []
        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        """
        
        index = len(self.list)
        
        if self.dict[val] == -1:
            node = Node(val = val, pre = -1, nxt = -1)
            
            self.dict[val] = index
            self.list.append(node)
            
            return True
        else:
            pre = self.dict[val]
            node = Node(val = val, pre = pre, nxt = -1)
            
            # append to the existing bidirectional link
            
            preNode = self.list[pre]
            preNode.nxt = index
            
            self.dict[val] = index
            self.list.append(node)
            
            return False

    def remove(self, val: int) -> bool:
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        """
        
        if self.dict[val] == -1:
            return False
        
        # use the last item of self.list to replace the removed item
        # and update the the altered item indices
        
        index = self.dict[val]
        node = self.list[index]
        
        if node.pre == -1:
            self.dict[val] = -1
        else:
            # remove from the removed node's bidirectional linked list
            self.dict[val] = node.pre
            self.list[node.pre].nxt = -1
            
        tailIndex = len(self.list) - 1
        tailNode = self.list.pop()

        if index != tailIndex:
            self.list[index] = tailNode

            # update tailNode's bidirectional linked list
            if self.dict[tailNode.val] == tailIndex:
                self.dict[tailNode.val] = index

            if tailNode.pre != -1:
                self.list[tailNode.pre].nxt = index

            if tailNode.nxt != -1:
                self.list[tailNode.nxt].pre = index
                
        return True
    
    def getRandom(self) -> int:
        """
        Get a random element from the collection.
        """
        
        index = random.randint(0, len(self.list) - 1)
        return self.list[index].val


# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

P.S. We can also use hash set to save all list item indices of a given value. Deleting item from hash set is also O(1).