Palindrome Partitioning (Java)

LeetCode

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

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution: DFS, Recursion

declare start point st, make it move from 0-> s.length(), for each st, check every substring generated by st and i, st+1<=i<=s.length(), if the substring is a palindrome then put it into ArrayList<String>  partition, if st reach s.length() mean we got a valid partition for given string s, then put it into ArrayList<ArrayList<String>> result;

Edit Distance (Java)

LeetCode

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Reverse Nodes in k-Group (Java)

LeetCode

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5  




solution to solve this question is easy to come out(just reverse list in 

certain range),however, coding this question elegantly is not a easy task. 

I spend much time on writing this question, but the code is not easy for 

reading. After search Internet, I find an very good version below.  

http://www.cnblogs.com/lichen782/p/leetcode_Reverse_Nodes_in_kGroup.html

Longest Substring Without Repeating Characters (Java)

Leetcode

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Distinct Subsequences (Java)

LeetCode

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

Solution: when see question about two strings , DP should be considered first. we can abstract this question to calculate appear times for string T with length i in string S with length j, which can be represented by numbers[i][j], then through observation and thinking , we can know for numbers[i][j] it should at least equal the numbers[i][j-1] and if T.charAt(i)==S.charAt(j) , numbers[i][j] should also be add numbers[i-1][j-1]

Combination Sum II (Java)

LeetCode

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] 

Solution: DFS

     Apply DFS continually check every combination, if any one meet the target put it into result arraylist.

Jump Game II (java)

LeetCode

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Solution: Greedy

At first, I try to solve this problem with DFS, but exceeded the time limitation, then I search the Internet find a very good solution for this question - Greedy Algorithm. the main idea is try to find the longest distance by each jump can reach and check if this distance can pass the total length of this array, of course we should have a variable to keep record of the current steps. if this distance cannot pass the total length of this array, then we should go through all the position within this distance to see if it can pass the array by jumping from there

I think code should be more clear than my description 

Add Two Numbers (Java)

LeetCode

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution: use two references point to the head of each list and add them and carry one by one. 

Sqrt(x) (Java)

Leetcode

Implement int sqrt(int x).

Compute and return the square root of x.

Solution: remember that the sqrt of an number must less than  its half, than we we can apply binary search to find our target. pleas don't forget the overflow risk

First Missing Positive (Java)

LeetCode

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Rotate List (Java)

LeetCode

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Solution: when see  an ListNode question, recursion, two pointers  and link head and tail are always common ways to considered about.

In this question, link head and tail is a good choice. First, use an extra reference to go from head to tail meanwhile count the length of this list. once we got the length and the tail , we can do two things, one is linked the tail with head, another is calculate k depend on given n and the length of list, k is how many nodes should be move right. k=len-n%len; After we finished these two things, 

we can place an preHead reference at tail and let it go next k steps, then preHead will be the point just ahead our target head. then return break the list here and return our target head. 

Valid Palindrome (Java)

LeetCode

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.

Solution: Two Pointers 

when you see this question, you should intuitively come out an two pointers solution, however, only alphanumeric characters need be considered depend on the question's description,  so we should use relative elegant way to check the validity of each character. 

Scramble String (Java)

Scramble String

 Total Accepted: 3103 Total Submissions: 15043

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":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

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".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

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".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

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.