Problem Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order. Note that the same word in the dictionary may be reused multiple times in the segmentation. Examples Example 1: Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] Output: ["cats and dog","cat sand dog"] ...
Problem You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. The area of an island is the number of cells with a value 1 in the island. Return the maximum area of an island in grid. If there is no island, return 0. ...
Problem There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c. A province is a group of directly or indirectly connected cities and no other cities outside of the group. You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise. ...
Sum of Distances in Tree Problem Problem There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. Return an array answer of length n where answer[i] is the sum of the distances between the ith node in the tree and all other nodes. ...
Problem Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence. graph TD; A(3) --- B(5) & C(1) B --- D(6) & E(2) E --- F(7) & G(4) C --- H(9) & I(8) style D fill:#4682B4,stroke:#333,stroke-width:2px style F fill:#4682B4,stroke:#333,stroke-width:2px style G fill:#4682B4,stroke:#333,stroke-width:2px style H fill:#4682B4,stroke:#333,stroke-width:2px style I fill:#4682B4,stroke:#333,stroke-width:2px ...
Problem Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes). Examples Example 1: ...
Problem Given the root of an n-ary tree, return the postorder traversal of its nodes’ values. Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples) Examples Example 1: graph TD 1 --- A[3] & B[2] & C[4] A --- 5 & 6 (have to use A, B, C in mermaid to make the ordering of nodes better) ...
N-ary Tree Preorder Traversal Problem Problem Given the root of an n-ary tree, return the preorder traversal of its nodes’ values. Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples) Examples Example 1: graph TD 1 --- A[3] & B[2] & C[4] A --- 5 & 6 ...
Problem Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys. Rules for a valid pattern: Each pattern must connect at least m keys and at most n keys. All the keys must be distinct. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed. The order of keys used matters. ...
Problem Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix. For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal]. Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries. Solution Method 1 - Using Trie with map of children and DFS Trie Class We have already seen Map-based Trie Implementation, and also seen another implementation of trie here: Implement Trie Problem. ...