Longest Palindromic Substring

Problem

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

---

Idea

---

Solution

---

Scramble String

Problem

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

---

Idea

如果两个string：s1和s2可以满足在某一个位置i,满足以下任意一种情况：
1. s1[0-i]和s2[0-i]相等或者互为scramble, 且s1[i+1, n]和s2[i+1,n]相等或互为scramble
2. s1[0-i]和s2[n-i, n]相等或者互为scramble， 且s1[i+1,n]和s2[0, n-i-1]相等或互为scramble

---

Solution

---

Find Minimum in Rotated Array2

Problem

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.
The array may contain duplicates.

---

Idea

---

Solution

---

Word Ladder

Problem

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

---

Idea

---

Solution

---

Min Stack

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

---

Idea

两个stack,一个用来存最小的stack,一个用来存正常的stack

---

Solution

---

Binary Tree Zigzag Level Order Traversal

Problem

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:

---

Idea

用两个栈实现,依次往s1,s2插入，一个先插左子树再右子树，一个先插右子树再左子树，最后就能得到zigzag的遍历效果

---

Solution

---

Permutation ||

Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

---

Idea

---

Solution

---