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;

	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"]
	]
	public class PalindromePartitioning {
	public ArrayList<ArrayList<String>> partition(String s) {
	ArrayList<ArrayList<String>> result=new ArrayList<ArrayList<String>>();
	if (s==null||s.length()==0){
	return result;
	}
	int st=0;
	ArrayList<String> partition=new ArrayList<String>();
	buildResult(s, st, partition, result);
	return result;
	}
	private void buildResult(String s, int st, ArrayList<String> partition, ArrayList<ArrayList<String>> result){
	if (st==s.length()){
	ArrayList<String> temp=new ArrayList<String>(partition);
	result.add(temp);
	return;
	}
	for (int i=st+1; i<=s.length(); i++){
	String tempStr=s.substring(st, i);
	if (isPalindrome(tempStr)){
	partition.add(tempStr);
	buildResult(s, i, partition, result );
	partition.remove(partition.size()-1);
	}
	}
	}
	private boolean isPalindrome(String str){
	int left=0;
	int right=str.length()-1;
	while (left<right){
	if (str.charAt(left)!=str.charAt(right)){
	return false;
	}
	left++;
	right--;
	}
	return true;
	}
	}

view raw PalindromePartitioning.java hosted with ❤ by GitHub

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

	"Take advantage of dp"
	"declare a matrix with one extral row and column "
	"make the first row from 0->word2.length and first column from 0->word1.length"
	"then iterate from matrix[1][1] tp matrix[m][n] if word1.charAt(i-1)=word2.charAt(j-1) then matrix[i][j]=matrix[i-1][j-1]"
	"else matix[i][j]=min(matrix[i-1][j]+1, matrix[i][j-1]+1, matrix[i-1][j-1]+1)"
	"Time complexity:O(mn)"
	public class Solution {
	public int minDistance(String word1, String word2) {
	// Start typing your Java solution below
	// DO NOT write main() function
	int m=word1.length();
	int n=word2.length();
	int[][] matrix=new int[m+1][n+1];
	for (int i=0; i<m+1; i++){
	matrix[i][0]=i;
	}
	for (int j=0; j<n+1; j++){
	matrix[0][j]=j;
	}
	for(int i=1; i<m+1; i++){
	for (int j=1; j<n+1; j++){
	if (word1.charAt(i-1)==word2.charAt(j-1)){
	// current char in word1 is equal to char in word2, mean no change at this step.
	//nums[i][j] is nums[i-1][j-1](mean the min times of change word1 to word2 without considering current chars)
	matrix[i][j]=matrix[i-1][j-1];
	}
	else{
	// nums[i-1][j-1] +1 is times of using replacement at this step
	// nums[i-1][j]+1 is times of using insert at this step
	// nums[i][j-1]+1 is times of using delete at this step
	matrix[i][j]=Math.min(matrix[i-1][j-1]+1,
	Math.min(matrix[i-1][j]+1, matrix[i][j-1]+1));
	}
	}
	}
	return matrix[m][n];
	}
	}

view raw Edit Distance.java hosted with ❤ by GitHub

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

	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
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	public ListNode reverseKGroup(ListNode head, int k) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (head ==null || k==1){
	return head;
	}
	ListNode dummy =new ListNode (0);
	dummy.next=head;
	ListNode pre=dummy;
	int i=0;
	while (head!=null){
	i++;
	if (i%k==0){
	pre=reverse(pre,head.next);
	head=pre.next;
	}
	else {
	head=head.next;
	}
	}
	return dummy.next;
	}
	/**
	* Reverse a link list between pre and next exclusively
	* an example:
	* a linked list:
	* 0->1->2->3->4->5->6
	* | |
	* pre next
	* after call pre = reverse(pre, next)
	*
	* 0->3->2->1->4->5->6
	* | |
	* pre next
	* @param pre
	* @param next
	* @return the reversed list's last node, which is the precedence of parameter next
	*/
	public ListNode reverse(ListNode pre, ListNode next){
	ListNode last=pre.next;
	ListNode cur=last.next;
	while (cur!=next){
	last.next=cur.next;
	cur.next=pre.next;
	pre.next=cur;
	cur=last.next;
	}
	return last;
	}
	}

view raw Reverse Nodes in k-Group.java hosted with ❤ by GitHub

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.

	"1/26/2014 code rewrite"
	public class LongestSuStringWithoutRepeatCharacter {
	public int lengthOfLongestSubstring(String s) {
	if (s==null ||s.length()==0){
	return 0;
	}
	// record which char has been visited
	boolean [] checker=new boolean[256];
	// two pointers used to maintain longest distance without repeat
	int st=0;
	int ed=0;
	// max length
	int max=0;
	while(ed<s.length()){
	char c=s.charAt(ed);
	// no repeat, up date checker and max length
	if (!checker[c]){
	checker[c]=true;
	max=Math.max(ed-st+1,max);
	}
	else{
	// repeat happened, update checker, and make st pointer point to first unrepeat position
	while (s.charAt(st)!=c){
	checker[s.charAt(st)]=false;
	st++;
	}
	// skip the char cause repeat
	st++;
	}
	ed++;
	}
	return max;
	}
	}
	"For Brute Force Solution:"
	"To solve this question we can just use for loop to iterative substring from every "
	"position of this string and use a hashtable to help checking is there is a repeat"
	"character from current start position, if it is then break current loop and move "
	"forward 1 position for the begin position of substring, if not just put current"
	"character into hashtable.then current length of substring is the length of hashtable"
	"time complexity: O(n^2)"
	"space complexity: O(n);"
	import java.util.Hashtable;
	public class Solution {
	public int lengthOfLongestSubstring(String s) {
	if (s==null||s.length()==0) return 0;
	int maxlen=1;
	Hashtable<Character, Boolean> ht=new Hashtable<Character, Boolean>();
	for (int i=0; i<s.length(); i++){
	for (int j=i;j<s.length(); j++){
	if (ht.containsKey(s.charAt(j))){
	ht.clear();
	break;
	}
	else{
	ht.put(s.charAt(j),true);
	}
	int len=ht.size();
	if (len>maxlen){
	maxlen=len;
	}
	}
	}
	return maxlen;
	}
	}
	"More efficient Solution:"
	"assume the character composite the string is only ASCII, then we can build a Boolean[256] "
	"exist array for record if the character has appeared. if a character appeared, then from start point to"
	"the position(not include this position) may be maxlen , then we do once compare , then don’t forget mark"
	"all of the character before this repeat character in exist array as false. then both begin and end index "
	"increase 1. if current character not appeared, then we mark is as appeared in exist array, then end index"
	"increase 1. "
	"time complexity: O(n) (hint: Worst case: 2n because both begin and end index iterate once entire string)"
	"Space Complexity: O(n)"
	public class Solution {
	public int lengthOfLongestSubstring(String s) {
	Boolean [] exist =new Boolean [256];
	for (int i=0; i<256;i++){
	exist[i]=false;
	}
	int i=0;
	int j=0;
	int n=s.length();
	int maxlen=0;
	while(j<n){
	if (exist[s.charAt(j)]){
	maxlen=Math.max(maxlen,j-i);
	while(s.charAt(i)!=s.charAt(j)){
	exist[s.charAt(i)]=false;
	i++;
	}
	i++;
	j++;
	}
	else{
	exist[s.charAt(j)]=true;
	j++;
	}
	}
	return maxlen=Math.max(maxlen, n-i);
	}
	}

view raw LongestSuStringWithoutRepeatCharacter.java hosted with ❤ by GitHub

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]

	/*
	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.
	*/
	public class DistinctSubsequences {
	public int numDistinct(String S, String T) {
	if (S==null||S.length()==0||T==null&&T.length()==0){
	return 0;
	}
	if (S.length()<T.length()){
	return 0;
	}
	int[][] nums=new int[T.length()+1][S.length()+1];
	for (int row=0; row<nums.length;row++){
	// appear numbers of String T in String "";
	nums[row][0]=0;
	}
	for (int col=0; col<nums[0].length; col++){
	// appears numbers of String "" in String S;
	nums[0][col]=1;
	}
	for (int row=1; row<nums.length; row++){
	for (int col=1; col<nums[0].length; col++){
	// no matter if current char in S equal to current char in T
	// current matched times is at least equal to the times matched between T and S.substring(0, index(current Char))
	nums[row][col]=nums[row][col-1];
	// if current char in T matched current char in S, then nums[row][col] should also plus
	// the times matched between T.substring(0,index(current char) ) and S.substring(0, index(current char));
	if (S.charAt(col-1)==T.charAt(row-1)){
	nums[row][col]+=nums[row-1][col-1];
	}
	}
	}
	return nums[T.length()][S.length()];
	}
	}

view raw DistinctSubsequences.java hosted with ❤ by GitHub

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.

	/*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]
	*/
	public class CombinationSumII {
	public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (num==null||num.length==0){
	return result;
	}
	ArrayList<Integer> current=new ArrayList<Integer>();
	int start=0;
	Arrays.sort(num);
	buildResult(num,start, target, current, result);
	return result;
	}
	private void buildResult(int[] num, int start, int target, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result){
	if (target==0){
	ArrayList<Integer> temp=new ArrayList<Integer>(current);
	result.add(temp);
	return;
	}
	for (int i=start; i<num.length; i++){
	if (num[i]>target){
	continue;
	}
	current.add(num[i]);
	buildResult(num,i+1, target-num[i], current,result);
	current.remove(current.size()-1);
	while(i+1<num.length && num[i]==num[i+1]){
	i++;
	}
	}
	}
	}

view raw CombinationSumII.java hosted with ❤ by GitHub

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 

	/*
	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.)
	*/
	public class JumpGameII {
	public int jump(int[] A) {
	if (A==null||A.length==0){
	return -1;
	}
	if (A.length==1){
	return 0;
	}
	int minStep=0;
	int start=0;
	// current longest distance the jump can reach
	int end=A[start];
	// if current longest distance plus current postion passed the length of array
	// then return current minStep + 1;
	if (start+end>=A.length-1){
	return minStep+1;
	}
	while(end<A.length-1){
	minStep++;
	// record farest position can be reached by jump from position within current farest position
	int max=0;
	for (int i=start; i<=end; i++){
	int current=i+A[i];
	// pass the total length, return minStep+1,
	if (current>=A.length-1){
	return minStep+1;
	}
	max=Math.max(max, current);
	}
	// update start position(items in array are not negative, so end+1 is exist)
	start=end+1;
	// update the most far position can reached for next jump
	end=max;
	}
	return minStep;
	}
	}

view raw JumpGameII.java hosted with ❤ by GitHub

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. 

	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
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class AddTwoNumbers {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	if (l1==null){
	return l2;
	}
	if (l2==null){
	return l1;
	}
	ListNode preHead=new ListNode(-1);
	ListNode end=preHead;
	ListNode node1=l1;
	ListNode node2=l2;
	int carry=0;
	while(node1!=null || node2!=null ||carry!=0){
	int current=0;
	if (node1!=null){
	current+=node1.val;
	node1=node1.next;
	}
	if (node2!=null){
	current+=node2.val;
	node2=node2.next;
	}
	if (carry!=0){
	current+=carry;
	}
	end.next=new ListNode(current%10);
	end=end.next;
	carry=current/10;
	}
	return preHead.next;
	}
	}

view raw AddTwoNumbers.java hosted with ❤ by GitHub

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

	Implement int sqrt(int x).
	Compute and return the square root of x.
	Time complexity O(lgn)
	public class Sqrt {
	public int sqrt(int x) {
	if (x<0){
	return-1;
	}
	// in case of x==1
	long high=x/2+1;
	long low=0;
	while(low<=high){
	long mid=low+(high-low)/2;
	long sq=mid*mid;
	if (sq==(long)x){
	return (int)mid;
	}
	else if (sq<(long)x){
	low=mid+1;
	}
	else{
	high=mid-1;
	}
	}
	return (int)high;
	}
	}

view raw sqrt(x).java hosted with ❤ by GitHub

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.

	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.
	algorithm should run in O(n) time and uses constant space.
	public class Solution {
	public int firstMissingPositive(int[] A) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (A==null||A.length==0) return 1;
	int i=0;
	while (i<A.length){
	// Strongly be care of that beside check A[i]!=i, also check A[A[i]]!=A[i]
	// in case [1,1], if only check A[i]=i, there will be infinity loop
	if (0<=A[i] &&A[i]<A.length&&A[i]!=i&&A[A[i]]!=A[i]){
	// must assign A[A[i]] to temp instead of A[i] to temp or will infinity loop
	// int temp=A[i];
	// A[i]=A[A[i]];
	//A[A[i]]=temp;
	// see A[i] in A[A[i]] and A[i] has been changed
	// so temp will never been sign to the place you want
	int temp=A[A[i]];
	A[A[i]]=A[i];
	A[i]=temp;
	}
	else{
	i++;
	}
	}
	for (int j=1; j<A.length; j++){
	if (A[j]!=j) return j;
	}
	// after above for loop mean for each position the value is equal to its index
	// then if A[0]==A.length mean the missing position should be A.length+1
	// the missing position is A.length;
	if (A[0]==A.length) return A.length+1;
	else {
	return A.length;
	}
	}
	}

view raw First Missing Positive.java hosted with ❤ by GitHub

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. 

	/*
	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.
	*/
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class RotateList {
	public ListNode rotateRight(ListNode head, int n) {
	if (head==null|| n==0){
	return head;
	}
	int len=1;
	ListNode last=head;
	// calculate the lenght of given list
	while(last.next!=null){
	last=last.next;
	len++;
	}
	last.next=head;
	// Should considered the situtation that n larger than given list's length
	int k=len-n%len;
	ListNode preHead=last;
	// find the point which are previuse for our target head
	while(k>0){
	preHead=preHead.next;
	k--;
	}
	head=preHead.next;
	preHead.next=null;
	return head;
	}
	}

view raw RotateList.java hosted with ❤ by GitHub

	/*
	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.
	*/
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class RotateList {
	public ListNode rotateRight(ListNode head, int n) {
	if (head==null|| n==0){
	return head;
	}
	int len=1;
	ListNode last=head;
	// calculate the lenght of given list
	while(last.next!=null){
	last=last.next;
	len++;
	}
	last.next=head;
	// Should considered the situtation that n larger than given list's length
	int k=len-n%len;
	ListNode preHead=last;
	// find the point which are previuse for our target head
	while(k>0){
	preHead=preHead.next;
	k--;
	}
	head=preHead.next;
	preHead.next=null;
	return head;
	}
	}

view raw RotateList.java hosted with ❤ by GitHub

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. 

	/*
	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.
	*/
	public class ValidPalindrome {
	public boolean isPalindrome(String s) {
	if (s==null){
	return false;
	}
	if (s.length()==0){
	return true;
	}
	s=s.toLowerCase();
	int left=0;
	int right=s.length()-1;
	while(left<right){
	// Skip all invalid character
	while(left<right && !isValid(s.charAt(left)))
	{
	left++;
	}
	// Skip all invalid character
	while( left<right && !isValid(s.charAt(right)))
	{
	right--;
	}
	if (s.charAt(left)!=s.charAt(right)) return false;
	left++;
	right--;
	}
	return true;
	}
	// check if current character is valid
	private boolean isValid(char c){
	if ('a'<=c && c<='z') return true;
	if ('0'<=c && c<='9') return true;
	return false;
	}
	}

view raw ValidPalindrome.java hosted with ❤ by GitHub

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.

	/*
	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.
	*/
	public class ScrambleString {
	public boolean isScramble(String s1, String s2) {
	if( s1==null||s2==null){
	return false;
	}
	if (s1.length()==0){
	return s2.length()==0;
	}
	if (s1.length()!=s2.length()){
	return false;
	}
	if (s1.equals(s2)){
	return true;
	}
	int value1=0;
	int value2=0;
	// check is s1 and s2 has same chars
	for (int i=0; i<s1.length(); i++){
	value1+=s1.charAt(i)-'0';
	value2+=s2.charAt(i)-'0';
	}
	if (value1!=value2){
	return false;
	}
	for (int i =1; i<s1.length(); i++){
	String s1Left=s1.substring(0, i);
	String s1Right=s1.substring(i);
	String s2Left=s2.substring(0,i);
	String s2Right=s2.substring(i);
	if (isScramble(s1Left, s2Left)&&isScramble(s1Right,s2Right)){
	return true;
	}
	s2Left=s2.substring(s2.length()-i);
	s2Right=s2.substring(0, s2.length()-i);
	if (isScramble(s1Left, s2Left)&&isScramble(s1Right,s2Right)){
	return true;
	}
	}
	return false;
	}
	}

view raw ScrambleString.java hosted with ❤ by GitHub

Maximal Rectangle (Java)

LeetCode

Maximal Rectangle

 Total Accepted: 2599 Total Submissions: 12591

Given a 2D binary matrix filled with 0's and 1's,

 find the largest rectangle containing all ones and 

return its area.

Similar question with largest rectangle in histogram but 

more tough.

we can apply a helper table to convert matrix to another

int[][] helper with calculate the current height for 1 at each 

column until current row.

Such as

char[][] matrix       -> int[][] helper

0,0,0,1,0                   0,0,0,1,0

0,1,1,0,1                   0,1,1,0,1

0,1,1,1,0                   0,2,2,1,0

0,0,1,0,1                   0,0,3, 0,1

then we can apply the method used in largest rectangle in

histogram to get max area which used current row as bottom

then keep updating max area.

	/*Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.*/
	public class MaximalRectangle {
	public int maximalRectangle(char[][] matrix) {
	if (matrix==null ||matrix.length==0){
	return 0;
	}
	int[][] heights=new int[matrix.length][matrix[0].length];
	// build heights table, once we have heights table, at each row, we can use
	// method which used in question of Largest Rectangle in Histogram to calculate
	// max area at until this row,.
	for (int row=0; row<matrix.length; row++){
	for (int col=0; col<matrix[0].length; col++){
	if (row==0){
	heights[row][col]=matrix[row][col]=='0'?0:1;
	}
	else{
	heights[row][col]=matrix[row][col]=='0'?0:heights[row-1][col]+1;
	}
	}
	}
	int max=0;
	for (int row=0; row<heights.length; row++){
	// update max with maxArea of each row
	max=Math.max(max, maxArea(heights[row]));
	}
	return max;
	}
	// calculate maxArea for each row
	private int maxArea(int[] heights){
	if (heights==null||heights.length==0){
	return 0;
	}
	Stack<Integer> stack=new Stack<Integer>();
	int max=0;
	int i=0;
	while(i<heights.length){
	if (stack.isEmpty()||heights[stack.peek()]<=heights[i]){
	stack.push(i);
	i++;
	}
	else{
	int height=heights[stack.pop()];
	int width=stack.isEmpty()?i:i-stack.peek()-1;
	max=Math.max(max, height*width);
	}
	}
	while(!stack.isEmpty()){
	int height=heights[stack.pop()];
	int width=stack.isEmpty()?i:i-stack.peek()-1;
	max=Math.max(max, height*width);
	}
	return max;
	}
	}

view raw MaximalRectangle.java hosted with ❤ by GitHub

Copy List with Random Pointer (Java)

LeetCode

Copy List with Random Pointer

Total Accepted: 4935 Total Submissions: 24214

A linked list is given such that each node contains an additional random pointer which could point to

 any node in the list or null.

Return a deep copy of the list.

Similar problem(Clone Graph)

Solution: 

This is an interesting question. Deep copy a single linked list with only next reference is easy. 

but, the tricky point is how to connect the random reference, we can not know if the node connected by the random reference exists or not when we copy node one by one. So to solve this problem, I think hashmap should be a good solution. With hashMap,do first while loop,  we copy every node in given list and keep them as a <originalNode, copiedNode> pair. then do another while loop connect these copied nodes together.

	/*
	A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
	Return a deep copy of the list.
	*/
	/**
	* Definition for singly-linked list with a random pointer.
	* class RandomListNode {
	* int label;
	* RandomListNode next, random;
	* RandomListNode(int x) { this.label = x; }
	* };
	*/
	public class Solution {
	public RandomListNode copyRandomList(RandomListNode head) {
	if (head==null){
	return null;
	}
	return copy(head);
	}
	private RandomListNode copy(RandomListNode node){
	HashMap<RandomListNode, RandomListNode> hm=new HashMap<RandomListNode, RandomListNode>();
	RandomListNode p=node;
	// copy every node of give list and store it in hashmap
	while(p!=null){
	hm.put(p, new RandomListNode(p.label));
	p=p.next;
	}
	p=node;
	RandomListNode head=null;
	RandomListNode current=null;
	// connect every node with next and random references
	while (p!=null){
	if (head==null){
	head=hm.get(p);
	current=head;
	}
	else{
	current.next=hm.get(p);
	current=current.next;
	}
	if (p.random!=null){
	current.random=hm.get(p.random);
	}
	p=p.next;
	}
	return head;
	}
	}

view raw CopyListWithRandomPointer .java hosted with ❤ by GitHub

Insert Interval (Java)

[LeetCode]

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

      This question is very similar with merge intervals. because the intervals is initially sorted according to their start times, so what we should do is just go through every interval in intervals list and put the smaller un-overlap interval into result list and updated current newInterval until to the end. But do not forget to add last newInterval into result list. See code below

	Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
	You may assume that the intervals were initially sorted according to their start times.
	Example 1:
	Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
	Example 2:
	Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
	This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
	/**
	* Definition for an interval.
	* public class Interval {
	* int start;
	* int end;
	* Interval() { start = 0; end = 0; }
	* Interval(int s, int e) { start = s; end = e; }
	* }
	*/
	public class InsertInterval {
	public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
	ArrayList<Interval> result=new ArrayList<Interval>();
	if (newInterval==null){
	return intervals;
	}
	if (intervals==null||intervals.size()==0){
	result.add(newInterval);
	return result;
	}
	for (Interval temp: intervals){
	if (temp.end<newInterval.start){
	result.add(temp);
	}
	else if (temp.start>newInterval.end){
	result.add(newInterval);
	newInterval=temp;
	}
	else{
	newInterval.start=Math.min(newInterval.start, temp.start);
	newInterval.end=Math.max(newInterval.end, temp.end);
	}
	}
	result.add(newInterval);
	return result;
	}
	}

view raw InsertInterval.java hosted with ❤ by GitHub

Implement strStr(). Java

LeetCode

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

	/*
	Implement strStr().
	Returns a pointer to the first occurrence of needle in haystack,
	or null if needle is not part of haystack.
	*/
	public class StrStr {
	public String strStr(String haystack, String needle) {
	if (haystack==null||needle==null){
	return null;
	}
	if (haystack.length()==0){
	if (needle.length()==0){
	return haystack;
	}
	else{
	return null;
	}
	}
	if (needle.length()==0){
	return haystack;
	}
	if (haystack.length()<needle.length()){
	return null;
	}
	// below code is a modified version of code in /**/ below, idea from a google+ friend.
	if (i>=0){
	return haystack.substring(i);
	}
	else{
	return null;
	}
	/*
	int i=0;
	int len=haystack.length()-needle.length();
	while(i<=len){
	if (haystack.charAt(i)==needle.charAt(0)){
	if (haystack.substring(i, i+needle.length()).equals(needle)){
	return haystack.substring(i);
	}
	}
	i++;
	}
	return null;
	*/
	}
	}
	// without use substring()
	public class Solution {
	public String strStr(String haystack, String needle) {
	// Start typing your Java solution below
	// DO NOT write main() function
	assert(haystack!=null && needle!=null);
	if (needle.length()==0){
	return haystack;
	}
	int i=0;
	while (i<haystack.length()){
	if (haystack.length()-i<needle.length()){
	break;
	}
	if (haystack.charAt(i)==needle.charAt(0)){
	int j=i;
	while (j-i<needle.length()&&needle.charAt(j-i)==haystack.charAt(j)){
	j++;
	if (j-i==needle.length()){
	return haystack.substring(i);
	}
	}
	}
	i++;
	}
	return null;
	}
	}

view raw StrStr.java hosted with ❤ by GitHub

Sudoku Solver (Java)

LeetCode

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

Solution: declare a function called isValid used to check if num from 1->9 will not conflict with nums which were already existed in the board, if it isValid, then recursively  call solved function to check if the board can be finally filled.

	/*
	Write a program to solve a Sudoku puzzle by filling the empty cells.
	Empty cells are indicated by the character '.'.
	You may assume that there will be only one unique solution.
	*/
	public class SudokuSolver {
	public void solveSudoku(char[][] board) {
	if (board==null||board.length==0){
	return;
	}
	solved(board);
	}
	private boolean solved(char[][] board){
	for(int i=0; i<board.length; i++){
	for (int j=0; j<board[0].length; j++){
	if (board[i][j]=='.'){
	for (char num='1'; num<='9'; num++){
	if(isValid(board, i, j, num)){
	// no conflict
	board[i][j]=num;
	if (solved(board)){
	return true;
	}
	else{
	board[i][j]='.';
	}
	}
	}
	// if no proper number found, return false
	return false;
	}
	}
	}
	return true;
	}
	private boolean isValid(char[][] board, int i, int j, char c){
	// check column
	for (int row=0; row<9; row++){
	if (board[row][j]==c){
	return false;
	}
	}
	// check row
	for (int col=0; col<9; col++){
	if (board[i][col]==c){
	return false;
	}
	}
	// check block
	for(int row=i/3*3; row<i/3*3+3; row++){
	for (int col=j/3*3; col<j/3*3+3; col++){
	if (board[row][col]==c){
	return false;
	}
	}
	}
	return true;
	}
	}

view raw SudokuSolver.java hosted with ❤ by GitHub

Clone Graph (Java)

LeetCode

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution: DFS traverse all nodes, meanwhile use HashMap to record the node which has been cloned. use label as key and the new created node as value

	Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
	OJ's undirected graph serialization:
	Nodes are labeled uniquely.
	We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
	As an example, consider the serialized graph {0,1,2#1,2#2,2}.
	The graph has a total of three nodes, and therefore contains three parts as separated by #.
	First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
	Second node is labeled as 1. Connect node 1 to node 2.
	Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
	Visually, the graph looks like the following:
	1
	/ \
	/ \
	0 --- 2
	/ \
	\_/
	/**
	* Definition for undirected graph.
	* class UndirectedGraphNode {
	* int label;
	* ArrayList<UndirectedGraphNode> neighbors;
	* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
	* };
	*/
	public class Solution {
	public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
	if (node==null){
	return null;
	}
	HashMap<Integer, UndirectedGraphNode> checker=new HashMap<Integer, UndirectedGraphNode>();
	return clone(node, checker);
	}
	private UndirectedGraphNode clone (UndirectedGraphNode node, HashMap<Integer, UndirectedGraphNode> checker){
	if (checker.containsKey(node.label)){
	return checker.get(node.label);
	}
	UndirectedGraphNode newNode=new UndirectedGraphNode(node.label);
	checker.put(newNode.label,newNode);
	for (UndirectedGraphNode tempNode: node.neighbors){
	newNode.neighbors.add(clone(tempNode, checker));
	}
	return newNode;
	}
	}

view raw CloneGraph.java hosted with ❤ by GitHub

Merge Intervals (Java)

LeetCode

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution:

Sort the list base on start valuable in an interval, then a while loop merge every overlap interval.

	Given a collection of intervals, merge all overlapping intervals.
	For example,
	Given [1,3],[2,6],[8,10],[15,18],
	return [1,6],[8,10],[15,18].
	/**
	* Definition for an interval.
	* public class Interval {
	* int start;
	* int end;
	* Interval() { start = 0; end = 0; }
	* Interval(int s, int e) { start = s; end = e; }
	* }
	*/
	public class MergeIntervals {
	public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
	if (intervals==null ||intervals.size()<2){
	return intervals;
	}
	ArrayList<Interval> result=new ArrayList<Interval>();
	Comparator<Interval> intervalComperator=new Comparator<Interval>(){
	public int compare(Interval i1, Interval i2){
	Integer i1St=i1.start;
	Integer i2St=i2.start;
	return i1St.compareTo(i2St);
	}
	};
	Collections.sort(intervals, intervalComperator);
	Interval current=intervals.get(0);
	int i=1;
	while (i<intervals.size() ){
	Interval currentToCompare=intervals.get(i);
	if (current.end<currentToCompare.start){
	result.add(current);
	current=currentToCompare;
	}
	else{
	current.end=Math.max(current.end, currentToCompare.end);
	}
	i++;
	}
	result.add(current);
	return result;
	}
	}

view raw MergeIntervals.java hosted with ❤ by GitHub

Restore IP Addresses (Java)

LeetCode

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Solution:

DFS to combine each possible result, meanwhile skip all impossible combination for result, such as

rest letters in s can not be more than 3* rest parts and rest letters can not be less than rest parts.

	/*
	Given a string containing only digits,
	restore it by returning all possible valid IP address combinations.
	For example:
	Given "25525511135",
	return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
	*/
	public class RestoreIPAddresses {
	public ArrayList<String> restoreIpAddresses(String s) {
	ArrayList<String> result=new ArrayList<String>();
	if (s==null||s.length()>12|| s.length()<4){
	return result;
	}
	String ip="";
	// record current index of s
	int i=0;
	// ip can be split into 4 parts, parNum is indicated which part it is
	int partNum=0;
	// DFS
	buildResult(s, i,ip, partNum, result);
	return result;
	}
	private void buildResult(String s, int i, String ip, int partNum, ArrayList<String> result){
	if (i==s.length() && partNum==4){
	StringBuilder sb=new StringBuilder(ip);
	sb.deleteCharAt(sb.length()-1);
	result.add(sb.toString());
	return;
	}
	int num=0;
	for (int j=i; j<i+3 && j<s.length(); j++){
	if (s.length()-j<4-partNum){
	// left letter number less than the need to fill all left parts
	return;
	}
	if (s.length()-j>(4-partNum)*3){
	// left parts can not hold all left letters
	return;
	}
	num=num*10+(s.charAt(j)-'0');
	if (num<=255){
	ip+=s.charAt(j);
	buildResult(s, j+1, ip+'.', partNum+1, result );
	}
	// skill all situation that the head of each part is start with 0, except only 0
	// at this section.
	/*
	example:
	Input: "010010"
	Output: ["0.1.0.0110","0.1.00.110","0.1.001.0","0.110.0.110","0.110.01.0","0.110100.1.0","01.0.0.110","01.0.01.0","01.00.1.0","0110.0.1.0"]
	Expected: ["0.10.0.10","0.100.1.0"]
	*/
	if (num==0){
	break;
	}
	}
	}
	}

view raw RestoreIPAddresses.java hosted with ❤ by GitHub

Valid Number ( Java )

LeetCode

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

This is really a trivial question, a lot of corner cases need to be found, just like the Stirng to Integer question.

	/*
	Validate if a given string is numeric.
	Some examples:
	"0" => true
	" 0.1 " => true
	"abc" => false
	"1 a" => false
	"2e10" => true
	Note: It is intended for the problem statement to be ambiguous.
	You should gather all requirements up front before implementing one.
	*/
	public class ValidNumber {
	public boolean isNumber(String s) {
	if (s==null ){
	return false;
	}
	// trim off head and tail zeros which not affect result depend on question
	s=s.trim();
	if(s.length()==0){
	return false;
	}
	boolean hasNum=false;
	boolean canSign=true;
	boolean canDot=true;
	boolean canE=false;
	boolean hasE=false;
	int i=0;
	while(i<s.length()){
	char c=s.charAt(i++);
	if (c==' '){
	return false;
	}
	if (c=='+' ||c=='-'){
	if (!canSign){
	return false;
	}
	canSign=false;
	continue;
	}
	if (c=='.'){
	if (!canDot){
	return false;
	}
	canDot=false;
	canSign=false;
	continue;
	}
	if (c=='e'){
	if (!canE||hasE){
	return false;
	}
	canE=false;
	hasE=true;
	hasNum=false;
	canDot=false;
	canSign=true;
	continue;
	}
	if (c>='0' && c<='9'){
	hasNum=true;
	if (!canE&&!hasE){
	canE=true;
	}
	canSign=false;
	}
	else{
	return false;
	}
	}
	return hasNum;
	}
	}

view raw ValidNumber.java hosted with ❤ by GitHub

Largest Rectangle in Histogram (Java)

LeetCode

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Solution:

similar questions(Longest Valid Parentheses, Maximal Rectangle)

Maintain a stack which used to record bar's indexes, in order to reach max increasing  bars until an shorter bar come,  then we calculate the  area of each situation consist by the bars in our stack. Because there may a coupe bars left in our stack, so don't forget calculate  them after first while loop.  

	public class LargestRectangleInHistogram {
	public int largestRectangleArea(int[] height) {
	if ( height==null||height.length==0){
	return 0;
	}
	Stack<Integer> stack=new Stack<Integer>();
	int max=0;
	int i=0;
	while(i<height.length){
	if (stack.isEmpty()||height[i]>=height[stack.peek()]){
	stack.push(i);
	i++;
	}
	else{
	int h=height[stack.pop()];
	int wid=stack.isEmpty()?i:i-stack.peek()-1;
	max=Math.max(h*wid, max);
	}
	}
	while (!stack.isEmpty()){
	int h=height[stack.pop()];
	int wid=stack.isEmpty()?i:i-stack.peek()-1;
	max=Math.max(h*wid, max);
	}
	return max;
	}
	}

view raw LargestRectangleInHistogram.java hosted with ❤ by GitHub