We can represent a sentence as an array of words, for example, the sentence “I am happy with leetcode” can be represented as arr = [“I”,“am”,happy",“with”,“leetcode”]. Given two sentences sentence1 and sentence2 each represented as a string array and given an array of string pairs similarPairs where similarPairs[i] = [xi, yi] indicates that the two words xi and yi are similar. Return true if sentence1 and sentence2 are similar, or false if they are not similar. ...
![https://leetcode.com/problems/remove-outermost-parentheses/] There are n computers numbered from 0 to n-1 connected by ethernet cables connections forming a network where connections[i] = [a, b] represents a connection between computers a and b. Any computer can reach any other computer directly or indirectly through the network. Given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected. If it’s not possible, return -1. ...
![https://leetcode.com/problems/longest-consecutive-sequence/] Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. Example 1: Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. Example 2: Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9 Constraints: 0 <= nums.length <= 104 -109 <= nums[i] <= 109 class Solution { public int longestConsecutive(int[] nums) { Map<Integer, Integer> valueToIndex = new HashMap<>(); UF uf = new UF(nums.length); for (int i = 0; i < nums.length; i++) { int value = nums[i]; if (valueToIndex.containsKey(value)) { continue; } if (valueToIndex.containsKey(value - 1)) { uf.union(i, valueToIndex.get(value - 1)); } if (valueToIndex.containsKey(value + 1)) { uf.union(i, valueToIndex.get(value + 1)); } valueToIndex.put(value, i); } return uf.maxSize; } static class UF { private int[] a; private int[] sz; private int maxSize = 0; UF(int n) { this.a = new int[n]; this.sz = new int[n]; for (int i = 0; i < n; i++) { a[i] = i; sz[i] = 1; maxSize = 1; } } void union(int p, int q) { int pid = find(p); int qid = find(q); if (sz[pid] > sz[qid]) { a[qid] = pid; sz[pid] += sz[qid]; maxSize = Math.max(maxSize, sz[pid]); } else { a[pid] = qid; sz[qid] += sz[pid]; maxSize = Math.max(maxSize, sz[qid]); } } int find(int p) { while (p != a[p]) { p = a[p]; } return p; } } }
![https://leetcode.com/problems/accounts-merge/] Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name. ...
![https://leetcode.com/problems/smallest-string-with-swaps/] You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string. You can swap the characters at any pair of indices in the given pairs any number of times. Return the lexicographically smallest string that s can be changed to after using the swaps. Example 1: Input: s = "dcab", pairs = [[0,3],[1,2]] Output: "bacd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[1] and s[2], s = "bacd" Example 2: Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]] Output: "abcd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[0] and s[2], s = "acbd" Swap s[1] and s[2], s = "abcd" Example 3: Input: s = "cba", pairs = [[0,1],[1,2]] Output: "abc" Explaination: Swap s[0] and s[1], s = "bca" Swap s[1] and s[2], s = "bac" Swap s[0] and s[1], s = "abc" Constraints: ...
![https://leetcode.com/problems/is-graph-bipartite/] Given an undirected graph, return true if and only if it is bipartite. Recall that a graph is bipartite if we can split its set of nodes into two independent subsets A and B, such that every edge in the graph has one node in A and another node in B. The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice. ...
![https://leetcode.com/problems/satisfiability-of-equality-equations/] Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: “a==b” or “a!=b”. Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names. Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations. Example 1: Input: ["a==b","b!=a"] Output: false Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second. There is no way to assign the variables to satisfy both equations. Example 2: Input: ["b==a","a==b"] Output: true Explanation: We could assign a = 1 and b = 1 to satisfy both equations. Example 3: Input: ["a==b","b==c","a==c"] Output: true Example 4: Input: ["a==b","b!=c","c==a"] Output: false Example 5: Input: ["c==c","b==d","x!=z"] Output: true Note: ...
![https://leetcode.com/problems/surrounded-regions/] Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’. A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region. Example: X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X Explanation: ...
![https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/] On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone. A stone can be removed if it shares either the same row or the same column as another stone that has not been removed. Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed. ...
![https://leetcode.com/problems/number-of-provinces/] 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. ...