Press "Enter" to skip to content

Posts tagged as “medium”

花花酱 LeetCode 211. Design Add and Search Words Data Structure

By zxi on December 5, 2021

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation 
WordDictionary wordDictionary = new WordDictionary(); 
wordDictionary.addWord("bad"); 
wordDictionary.addWord("dad"); 
wordDictionary.addWord("mad"); 
wordDictionary.search("pad"); // return False 
wordDictionary.search("bad"); // return True 
wordDictionary.search(".ad"); // return True 
wordDictionary.search("b.."); // return True

Constraints:

  • 1 <= word.length <= 500
  • word in addWord consists lower-case English letters.
  • word in search consist of  '.' or lower-case English letters.
  • At most 50000 calls will be made to addWord and search.

Solution: Hashtables

The first hashtable stores all the words, if there is no dot in the search pattern. Do a full match.

There are also per length hashtable to store words of length k. And do a brute force match.

Time complexity: Init: O(n*l)
search: best: O(l) worst: O(n*l)

C++

花花酱 LeetCode 205. Isomorphic Strings

By zxi on December 5, 2021

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Constraints:

  • 1 <= s.length <= 5 * 104
  • t.length == s.length
  • s and t consist of any valid ascii character.

Solution: Counting

The # of distinct pairs e.g. (s[i], t[i]), should be equal to the # of distinct chars in s and t.
ex1:
set of pairs: {(e, a), (g,d)}
set of s: {e, g}
set of t: {a, d}
For s, we can replace e with a, and replace g with d.
ex2:
set of pairs: {(f, b), (o, a), (o, r)}
set of s: {f, o}
set of t: {b, a, r}
o can not pair with a, r at the same time.
ex3:
set of pairs: {(p, t), (a, i), (e, l), (r, e)}
set of s: {p, a, e, r}
set of t: {t, i, l, e}

Time complexity: O(n)
Space complexity: O(256*256)

C++

花花酱 LeetCode 201. Bitwise AND of Numbers Range

By zxi on December 5, 2021

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Constraints:

  • 0 <= left <= right <= 231 - 1

Solution: Bit operation

Bitwise AND all the numbers between left and right will clear out all the low bits. Basically this question is asking to find the common prefix of left and right in the binary format.


5 = 0b0101
7 = 0b0111
the common prefix is 0b0100 which is 4.

Time complexity: O(logn)
Space complexity: O(1)

C++

花花酱 LeetCode 2096. Step-By-Step Directions From a Binary Tree Node to Another

By zxi on December 5, 2021

You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.

Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:

  • 'L' means to go from a node to its left child node.
  • 'R' means to go from a node to its right child node.
  • 'U' means to go from a node to its parent node.

Return the step-by-step directions of the shortest path from node s to node t.

Example 1:

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.

Example 2:

Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation: The shortest path is: 2 → 1.

Constraints:

  • The number of nodes in the tree is n.
  • 2 <= n <= 105
  • 1 <= Node.val <= n
  • All the values in the tree are unique.
  • 1 <= startValue, destValue <= n
  • startValue != destValue

Solution: Lowest common ancestor

It’s no hard to see that the shortest path is from the start node to the lowest common ancestor (LCA) of (start, end), then to the end node. The key is to find the LCA while finding paths from root to two nodes.

We can use recursion to find/build a path from root to a target node.
The common prefix of these two paths is the path from root to the LCA that we need to remove from the shortest path.
e.g.
root to start “LLRLR”
root to dest “LLLR”
common prefix is “LL”, after removing, it becomes:
LCA to start “RLR”
LCA to dest “LR”
Final path becomes “UUU” + “LR” = “UUULR”

The final step is to replace the L/R with U for the start path since we are moving up and then concatenate with the target path.

Time complexity: O(n)
Space complexity: O(n)

C++


花花酱 LeetCode 2095. Delete the Middle Node of a Linked List

By zxi on December 4, 2021

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

  • For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Example 1:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node.

Example 2:

Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Example 3:

Input: head = [2,1]
Output: [2]
Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

Constraints:

  • The number of nodes in the list is in the range [1, 105].
  • 1 <= Node.val <= 105

Solution: Fast / Slow pointers

Use fast / slow pointers to find the previous node of the middle one, then skip the middle one.

prev.next = prev.next.next

Time complexity: O(n)
Space complexity: O(1)

C++