# 2020-01-16

## 994. Rotting Oranges

### Descripsion

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell; the value 1 representing a fresh orange; the value 2 representing a rotten orange. Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

```
Example 1:
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
```

Note:

1 <= grid.length <= 10 1 <= grid[0].length <= 10 grid[i][j] is only 0, 1, or 2.

### Solution

```
class Solution {
//First, count fresh oranges. Then, until fresh is non-zero, perform BFS to rot oranges, decreasing fresh. Count days (d) and return it in the end. If, after another day, fresh does not change, return -1.
//For BFS, we can use the day counter (d + 2) to only process oranges that rotted yesterday.
public int orangesRotting(int[][] grid) {
int fresh = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
fresh++;
}
}
}
int day = 0;
for (int old_fresh = fresh; fresh > 0; old_fresh = fresh, day++) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
//only process rotted yesterday.
if (grid[i][j] == day + 2) {
fresh -= (rot(grid, i - 1, j, day) + rot(grid, i + 1, j, day) + rot(grid, i, j - 1, day) + rot(grid, i, j + 1, day));
}
}
}
//when still have fresh one but not able to rot it.
if (fresh == old_fresh) {
return -1;
}
}
return day;
}
private int rot(int[][] grid, int i, int j, int day) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] != 1) {
return 0;
}
//use day+3 to mark rotted, and only process the one rotted yesterday.
grid[i][j] = day + 3;
return 1;
}
}
```

## 543. Diameter of Binary Tree

### Description

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

```
Example:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
```

Note: The length of path between two nodes is represented by the number of edges between them.

### Solution

```
public class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return max;
}
private int maxDepth(TreeNode root) {
if (root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
}
}
```

## 733. Flood Fill

### Description

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image.

To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

```
Example 1:
Input:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation:
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.
```

Note:

The length of image and image[0] will be in the range [1, 50]. The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length. The value of each color in image[i][j] and newColor will be an integer in [0, 65535].

### Solution

```
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
//need to check, if it's the same, just return.
if(image[sr][sc] == newColor) return image;
fill(image,sr,sc,image[sr][sc],newColor);
return image;
}
private void fill(int[][] image, int sr, int sc, int color, int newcolor) {
if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[sr].length || image[sr][sc] != color) {
return;
}
image[sr][sc] = newcolor;
fill(image,sr+1,sc,color,newcolor);
fill(image,sr-1,sc,color,newcolor);
fill(image,sr,sc+1,color,newcolor);
fill(image,sr,sc-1,color,newcolor);
}
}
```

## 256. Paint House

### Description

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note: All costs are positive integers.

```
Example:
Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.
```

### Solution

```
class Solution {
public int minCost(int[][] costs) {
if(costs==null || costs.length == 0){
return 0;
}
int len = costs.length;
for(int i = 1; i<len;i++){
costs[i][0] += Math.min(costs[i-1][1],costs[i-1][2]);
costs[i][1] += Math.min(costs[i-1][0],costs[i-1][2]);
costs[i][2] += Math.min(costs[i-1][1],costs[i-1][0]);
}
return Math.min(costs[len-1][0],Math.min(costs[len-1][1],costs[len-1][2]));
}
}
```

## 725. Split Linked List in Parts

### Description

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”.

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode’s representing the linked list parts that are formed.

```
Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]
Example 1:
Input:
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it's string representation as a ListNode is [].
Example 2:
Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.
```

Note:

The length of root will be in the range [0, 1000]. Each value of a node in the input will be an integer in the range [0, 999]. k will be an integer in the range [1, 50].

### Solution

```
import java.util.List;
/**
* Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
*/
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode[] res = new ListNode[k];
int len = 0;
ListNode temp_count = root;
while (temp_count != null) {
len++;
temp_count = temp_count.next;
}
// n : minimum guaranteed part size;
// r : extra nodes spread to the first r parts;
int n = len / k;
int r = len % k;
ListNode node =root, prev = null;
for(int i = 0;node!=null && i<k;i++,r--){
res[i] = node;
for(int j = 0;j<n+(r>0?1:0);j++){
prev = node;
node =node.next;
}
prev.next = null;
}
return res;
}
}
```

# 2020-01-20

## 1114. Print in Order

### Description

Suppose we have a class:

public class Foo { public void first() { print(“first”); } public void second() { print(“second”); } public void third() { print(“third”); } } The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().

```
Example 1:
Input: [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.
Example 2:
Input: [1,3,2]
Output: "firstsecondthird"
Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.
```

Note:

We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seems to imply the ordering. The input format you see is mainly to ensure our tests’ comprehensiveness.

### Solution

```
/*
"Semaphore is a bowl of marbles" - Professor Stark
Semaphore is a bowl of marbles (or locks in this case). If you need a marble, and there are none, you wait. You wait until there is one marble and then you take it. If you release(), you will add one marble to the bowl (from thin air). If you release(100), you will add 100 marbles to the bowl (from thin air).
The thread calling third() will wait until the end of second() when it releases a '3' marble. The second() will wait until the end of first() when it releases a '2' marble. Since first() never acquires anything, it will never wait. There is a forced wait ordering.
With semaphores, you can start out with 1 marble or 0 marbles or 100 marbles. A thread can take marbles (up until it's empty) or put many marbles (out of thin air) at a time.
Upvote and check out my other concurrency solutions.
*/
import java.util.concurrent.Semaphore;
class Foo {
Semaphore run2, run3;
public Foo() {
run2 = new Semaphore(0);
run3 = new Semaphore(0);
}
public void first(Runnable printFirst) throws InterruptedException {
// printFirst.run() outputs "first". Do not change or remove this line.
printFirst.run();
run2.release();
}
public void second(Runnable printSecond) throws InterruptedException {
run2.acquire();
// printSecond.run() outputs "second". Do not change or remove this line.
printSecond.run();
run3.release();
}
public void third(Runnable printThird) throws InterruptedException {
run3.acquire();
// printThird.run() outputs "third". Do not change or remove this line.
printThird.run();
}
}
```

# 2020-01-21

## 697. Degree of an Array

### Description

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1: Input: [1, 2, 2, 3, 1] Output: 2 Explanation: The input array has a degree of 2 because both elements 1 and 2 appear twice. Of the subarrays that have the same degree: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] The shortest length is 2. So return 2. Example 2: Input: [1,2,2,3,1,4,2] Output: 6 Note:

nums.length will be between 1 and 50,000. nums[i] will be an integer between 0 and 49,999.

### Solution

```
import java.util.HashMap;
import java.util.Map;
class Solution {
/*
One pass on A,
For each different number a in A,
we need to count its frequency and it first occurrence index.
If a has the maximum frequency,
update the degree = count[a] and res = i - first[A[i]] + 1.
If a is one of the numbers that has the maximum frequency,
update the res = min(res, i - first[A[i]] + 1)
*/
public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> count = new HashMap<>(), firstIndex = new HashMap<>();
int degree = 0, res = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int n = nums[i];
//only store the first index of current number
firstIndex.putIfAbsent(n,i);
//count the current number.
count.put(n,count.getOrDefault(n,0)+1);
//if current number is larger, update degree
if(count.get(n)>degree){
degree = count.get(n);
//after update degree, need to update length of min subarray.
//the current number to the first index, it's may not be the final result
//if encounter this number again, will update.
//so will always calc the length from last to first index.
res = i-firstIndex.get(n) + 1;
}else if(count.get(n)==degree){
//encounter again, update.
res = Math.min(res,i-firstIndex.get(n)+1);
}
}
return res;
}
}
```

## 349. Intersection of Two Arrays

### Description

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2] Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] Note:

Each element in the result must be unique. The result can be in any order.

### Solution

```
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int len1 = nums1.length, len2 = nums2.length;
Set<Integer> set = new HashSet<>();
Arrays.sort(nums1);
for(int n: nums2){
//see Arrays doc.
if(Arrays.binarySearch(nums1,n)>=0){
set.add(n);
}
}
int[] res = new int[set.size()];
Iterator<Integer> iterator = set.iterator();
for(int i = 0;i<res.length;i++){
res[i] = iterator.next();
}
return res;
}
}
```

## 203. Remove Linked List Elements

### Dewcription

Remove all elements from a linked list of integers that have value val.

Example:

Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5

### Solution

```
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy, cur = head;
while(cur != null){
if(cur.val==val){
pre.next = cur.next;
}else{
pre = pre.next;
}
cur = cur.next;
}
return dummy.next;
}
}
```

## 23. Merge k Sorted Lists

### Description

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6

### Solution

```
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0){
return null;
}
PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.length, (o1,o2)->(o1.val - o2.val));
for(ListNode listNode : lists){
if(listNode != null){
pq.offer(listNode);
}
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(!pq.isEmpty()){
cur.next = pq.poll();
cur = cur.next;
if(cur.next != null){
pq.offer(cur.next);
}
}
return dummy.next;
}
}
```

## 208. Implement Trie (Prefix Tree)

### Description

Implement a trie with insert, search, and startsWith methods.

```
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
```

Note:

You may assume that all inputs are consist of lowercase letters a-z. All inputs are guaranteed to be non-empty strings.

### Solution

```
public class Trie {
private TrieNode root;
/** Initialize your data structure here. */
//like linked list.
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode ws = root;
char[] letters = word.toCharArray();
for(int i = 0;i<letters.length;i++){
char cur = letters[i];
if(ws.next[cur-'a'] == null){
ws.next[cur-'a'] = new TrieNode();
}
ws = ws.next[cur-'a'];
}
ws.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode ws = root;
char[] letters = word.toCharArray();
for(int i = 0;i<letters.length;i++){
char cur = letters[i];
if(ws.next[cur-'a'] == null){
return false;
}
ws = ws.next[cur-'a'];
}
return ws.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode ws = root;
char[] letters = prefix.toCharArray();
for(int i = 0;i<letters.length;i++){
char cur = letters[i];
if(ws.next[cur-'a'] == null){
return false;
}
ws = ws.next[cur-'a'];
}
return true;
}
}
class TrieNode{
boolean isWord;
TrieNode[] next;
public TrieNode(char c){
next = new TrieNode[26];
isWord = false;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
```

# 2020-01-27

## 309. Best Time to Buy and Sell Stock with Cooldown

### Description

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day) Example:

Input: [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]

### Solution

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/75928/Share-my-DP-solution-(By-State-Machine-Thinking)

```
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 1) return 0;
int len = prices.length;
int[] s0 = new int[len], s1 = new int[len],s2 = new int[len];
s0[0] = 0;
s1[0] = -prices[0];
s2[0] = Integer.MIN_VALUE;
for(int i = 1;i<len;i++){
s0[i] = Math.max(s0[i-1],s2[i-1]);
s1[i] = Math.max(s0[i-1]-prices[i],s1[i-1]);
s2[i] = s1[i-1] + prices[i];
}
return Math.max(s0[len-1],s2[len-1]);
}
}
```

# 2020-01-30

## 295. Find Median from Data Stream

### Description

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example, [2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure. double findMedian() - Return the median of all elements so far.

Example:

addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2

Follow up:

If all integer numbers from the stream are between 0 and 100, how would you optimize it? If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

### Solution

```
class MedianFinder {
PriorityQueue<Long> large, small;
/** initialize your data structure here. */
public MedianFinder() {
large = new PriorityQueue();
small = new PriorityQueue();
}
public void addNum(int num) {
large.add((long)num);
small.add(-large.poll());
if(large.size()<small.size()){
large.add(-small.poll());
}
}
public double findMedian() {
return large.size()>small.size()?large.peek():(large.peek()-small.peek())/2.0;
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
```

### follow up

If all integer numbers from the stream are between 0 and 100, how would you optimize it?

use an array of 100 to store the count and iterate over it.

If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

Use an array and a hashMap to count the total number and location.

## 212. Word Search II

### Description

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

```
Input:
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
```

Note:

All inputs are consist of lowercase letters a-z. The values of words are distinct.

### Solution

```
class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList();
TrieNode root = buildTrie(words);
for(int i = 0; i< board.length;i++){
for(int j = 0;j<board[0].length;j++){
dfs(board, i, j, root, res);
}
}
return res;
}
public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res){
if(i <0 || j<0 || i>=board.length || j >= board[0].length || board[i][j] == '#' || p.next[board[i][j]-'a']==null) return;
char c = board[i][j];
p = p.next[board[i][j]-'a'];
if(p.word != null){
res.add(p.word);
p.word = null;
}
board[i][j] = '#';
dfs(board, i-1, j, p, res);
dfs(board, i+1, j, p, res);
dfs(board, i, j-1, p, res);
dfs(board, i, j+1, p, res);
board[i][j] = c;
}
public TrieNode buildTrie(String[] words){
TrieNode root = new TrieNode();
for(String s: words){
TrieNode p = root;
for(char c: s.toCharArray()){
if(p.next[c-'a']==null) p.next[c-'a'] = new TrieNode();
p = p.next[c-'a'];
}
p.word = s;
}
return root;
}
class TrieNode{
TrieNode[] next = new TrieNode[26];
String word;
}
}
```

## 572. Subtree of Another Tree

### Description

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1: Given tree s:

```
3
/ \ 4 5 / \ 1 2 Given tree t: 4 / \ 1 2 Return true, because t has the same structure and node values with a subtree of s. Example 2: Given tree s:
3
/ \ 4 5 / \ 1 2
/ 0 Given tree t: 4 / \ 1 2 Return false.
```

### Solution

```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if(s == null || t == null) return false;
if(isSame(s,t)) return true;
return isSubtree(s.left,t) || isSubtree(s.right, t);
}
public boolean isSame(TreeNode s, TreeNode t){
if(s == null && t == null) return true;
if(s == null || t == null) return false;
if(s.val != t.val) return false;
return isSame(s.left, t.left) && isSame(s.right, t.right);
}
}
```

# 2020-01-31

## 140. Word Break II

### Description

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1:

```
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]
Example 2:
Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]
```

### Solution

```
class Solution {
HashMap<String, List<String>> map;
HashSet<String> wordSet;
public List<String> wordBreak(String s, List<String> wordDict) {
map = new HashMap();
wordSet = new HashSet(wordDict);
return helper(s);
}
public List<String> helper(String s){
List<String> res = new ArrayList();
if(s == null || s.isEmpty()) return res;
//if already searched, just return result.
if(map.containsKey(s)) return map.get(s);
//the left string is itself a word.
if(wordSet.contains(s)) {
res.add(s);
}
for(int i = 1;i<s.length();i++){
//cut the first i char as a word.
String t = s.substring(0, i);
if(wordSet.contains(t)){
//get all possible result of the left string.
List<String> temp = helper(s.substring(i));
if(temp!=null && temp.size()!=0){
//combine each of the result with t(word)
for(int j = 0;j<temp.size();j++){
res.add(t+" "+temp.get(j));
}
}
}
}
//store it to prevent duplication.
map.put(s,res);
return res;
}
}
```

## 348. Design Tic-Tac-Toe

### Description

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

A move is guaranteed to be valid and is placed on an empty block. Once a winning condition is reached, no more moves is allowed. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game. Example: Given n = 3, assume that player 1 is “X” and player 2 is “O” in the board.

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> Returns 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | |

toe.move(0, 2, 2); -> Returns 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins) |X| |O| | |O| | // Player 2 makes a move at (1, 1). | | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins) |X| |O| | |O| | // Player 1 makes a move at (2, 0). |X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins) |X| |O| |O|O| | // Player 2 makes a move at (1, 0). |X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins) |X| |O| |O|O| | // Player 1 makes a move at (2, 1). |X|X|X| Follow up: Could you do better than O(n2) per move() operation?

### Solution

```
class TicTacToe {
private int[] rows;
private int[] cols;
private int diag;
private int antidiag;
private int size;
/** Initialize your data structure here. */
public TicTacToe(int n) {
rows = new int[n];
cols = new int[n];
size = n;
}
/** Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins. */
public int move(int row, int col, int player) {
int toAdd = player==1?1:-1;
rows[row] += toAdd;
cols[col] += toAdd;
if(row==col){
diag += toAdd;
}
if(row+col == size - 1){
antidiag += toAdd;
}
if(Math.abs(rows[row])==size ||
Math.abs(cols[col])==size ||
Math.abs(diag)==size ||
Math.abs(antidiag)==size
) return player;
return 0;
}
}
/**
* Your TicTacToe object will be instantiated and called as such:
* TicTacToe obj = new TicTacToe(n);
* int param_1 = obj.move(row,col,player);
*/
```