Skip to content

Instantly share code, notes, and snippets.

View shailrshah's full-sized avatar
🖥️
Available

Shail Shah shailrshah

🖥️
Available
9 followers · 0 following
View GitHub Profile
@shailrshah
shailrshah / WordBreak.java
Created November 13, 2017 01:32
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
// wordBreak("facebook", ["face", "book"]) -> true
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
if(set.contains(s))
return true;
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.add(0);
visited.add(0);
@shailrshah
shailrshah / BinaryTreePaths.java
Created November 12, 2017 23:17
Given a binary tree, return all root-to-leaf paths.
public List<String> binaryTreePaths(TreeNode root) {
List<String> list = new ArrayList<>();
if(root != null)getPaths(root, list, "");
return list;
}
private static void getPaths(TreeNode root, List<String> list, String path) {
if(root.left == null && root.right == null) list.add(path + root.val);
if(root.left != null) getPaths(root.left, list, path + root.val + "->");
if(root.right != null) getPaths(root.right, list, path + root.val + "->");
@shailrshah
shailrshah / WildCard.java
Created November 12, 2017 22:40
Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial).
private static String getClean(String pattern){
StringBuilder sb = new StringBuilder();
sb.append(pattern.charAt(0));
for(int i = 1; i < pattern.length(); i++) {
char ch = pattern.charAt(i);
if(ch != '*') sb.append(ch);
else {
char lastChar = sb.charAt(sb.length()-1);
if(lastChar!='*') sb.append(ch);
@shailrshah
shailrshah / WordLength.java
Created November 12, 2017 15:52
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
int count = 1;
if(beginWord.equals(endWord))
return count;
Queue<String> queue = new LinkedList<>();
Set<String> set = new HashSet<String>(wordList); // contains() is O(1). For ArrayList it's O(n)
queue.add(beginWord);
set.remove(beginWord);
@shailrshah
shailrshah / CloneGraph.java
Created November 12, 2017 06:13
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
Map<Integer, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return null;
if(map.containsKey(node.label))
return map.get(node.label);
UndirectedGraphNode clonedNode = new UndirectedGraphNode(node.label);
map.put(clonedNode.label, clonedNode);
for(UndirectedGraphNode neighbor : node.neighbors)
clonedNode.neighbors.add(cloneGraph(neighbor));
@shailrshah
shailrshah / Skyline.java
Created November 12, 2017 03:59
https://leetcode.com/problems/the-skyline-problem/description/
import java.util.SortedMap;
class CriticalPoint implements Comparable<CriticalPoint>{
int x;
int y;
int isRightEnd;
CriticalPoint(int x, int y, int isRightEnd) {
this.x = x;
this.y = y;
this.isRightEnd = isRightEnd;
@shailrshah
shailrshah / SparseMatMul.java
Last active November 13, 2017 22:27
Given two sparse matrices A and B, return the result of AB. You may assume that A's column number is equal to B's row number.
/*
a[2][3]
1 2 3
4 5 6
b[3][2]
7 8
9 10
11 12
@shailrshah
shailrshah / MinSquare.java
Created November 11, 2017 21:20
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
// dp[0] = 0
// dp[i] = min(dp[n-i*i] + 1) where i > 0 && n-i*i >=0
public int numSquares(int n) {
int dp[] = new int[n+1];
dp[0] = 0;
for(int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
int j = 1;
@shailrshah
shailrshah / ReverseWords.java
Created November 10, 2017 02:05
Given a sentence delimited by spaces, reverse the sentence.
public String reverseWords(String s) {
String[] a = s.replaceAll("\\s+", " ").split(" ");
int i = 0, j = a.length-1;
while(i < j) {
String temp = a[i];
a[i++] = a[j];
a[j--] = temp;
}
return String.join(" ", a).trim();
@shailrshah
shailrshah / RemoveInvalidParentheses.java
Created November 9, 2017 02:19
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results. Note: The input string may contain letters other than the parentheses ( and ).
public List<String> removeInvalidParentheses(String s) {
List<String> list = new ArrayList<>();
backtrack(list, s, 0, 0, new char[]{'(', ')'});
return list;
}
private static void backtrack(List<String> list, String s, int iStart, int jStart, char[] par) {
int stack = 0;
for(int i = iStart; i < s.length(); i++) {
if(s.charAt(i) == par[0]) stack++;