Find Minimum in Rotated Sorted Array

Problem

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.
You may assume no duplicate exists in the array.

---

Idea

用二分查找[left,right], 每次二分的那个点pivot，一定会把数组分成一个有序的和一个无序的，最小值永远都在无序的那个里

---

Solution

---

Combination Sum ||

Problem

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,

A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

---

Idea

剪枝+dfs

---

Solution

---

Palindrome Partition

Problem

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

---

Idea

首先对字符串的所有子串判断是否是回文，设f[i][j] = true表示以i为起点，长度为j的子串是回文,等于false表示不是回文，那么求f[i][j]的动态规划方程如下：

当j = 1，f[i][j] = true;
当j = 2，f[i][j] = (s[i]==s[i+1]),其中s是输入字符串
当j > 2, f[i][j] = f[i+1][j-2] && (s[i] == s[i+j-1])（即判断s[m..n]是否是回文时：只要s[m+1...n-1]是回文并且s[m] = s[n]，那么它就是回文，否则不是回文）

---

Solution

---

Valid Palindrome

Problem

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

---

Idea

考虑大小写转化，以及数字的case例如: A2a,和 1a3

---

Solution

---

Word Search

Problem

Given a 2D board and a word, find if the word exists in the grid.

The word can 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.

For example,

---

Idea

DFS, 一次搜索上下左右,注意不能重复

---

Solution

---

Regular Expression Matching

Problem

Implement regular expression matching with support for '.' and '*'.

---

Idea

思路

---

Solution

---

Simplify Path

Problem

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".

---

Idea

---

Solution

---