Substring with Concatenation of All Words

Problem:

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

Analysis:

一开始觉得非常复杂，找了几个别人的博客看。看了几天，没看懂。最后找到一个牛人的地址http://n00tc0d3r.blogspot.com/2013/06/substring-with-concatenation-of-all.html?view=classic 慢慢的就懂了。不过有些细节还是不太清楚，只有慢慢积累。

现在开始把代码写到Eclipse里面了。1.可以节约在LeetCode编码的时间. 2. LeetCode如果报错可以Debug。之前一旦LeetCode没通过要找n久的bug，效率实在太低。

时间和空间复杂度就暂时不讨论了，不懂。

Solution:

1:  public class Solution {  
2:   public ArrayList<Integer> findSubstring(String S, String[] L){  
3:         ArrayList<Integer> res=new ArrayList<Integer>();  
4:         if(S==null||L==null)  
5:              return res;  
6:         HashMap<String,Integer> words=new HashMap<String,Integer>();  
7:         int wordLen=L[0].length(),total=L.length;  
8:         for(String s:L)//Store all words to hashmap  
9:         {  
10:              if(words.containsKey(s))  
11:                   words.put(s, words.get(s)+1);  
12:              else  
13:                   words.put(s, 1);  
14:         }  
15:         for(int i=0;i<=S.length()-wordLen*total;i++)  
16:         {  
17:              HashMap<String,Integer> curWords=new HashMap<String,Integer>(words);  
18:              for(int j=i;j<=S.length()-wordLen && !curWords.isEmpty();j+=wordLen)  
19:              {  
20:                   String word=S.substring(j,j+wordLen);  
21:                   if(!curWords.containsKey(word))  
22:                        break;  
23:                   else  
24:                   {  
25:                        if(curWords.get(word)>1)  
26:                             curWords.put(word, curWords.get(word)-1);  
27:                        else  
28:                             curWords.remove(word);  
29:                   }  
30:              }  
31:              if(curWords.isEmpty())  
32:                   res.add(i);  
33:         }  
34:       return res;  
35:    }  
36:  }  

Generate Parentheses

Problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Analysis:
DFS

Solution:

1:  public class Solution {  
2:    public ArrayList<String> generateParenthesis(int n) {  
3:      ArrayList<String> result=new ArrayList<String>();  
4:      DoDSF("",n,n,result);  
5:      return result;  
6:    }  
7:    private void DoDSF(String prefix, int left, int right, ArrayList<String> result)  
8:    {  
9:      if(left==0&& right==0)  
10:      {  
11:        result.add(prefix);  
12:        return;  
13:      }  
14:      if(left!=0)  
15:       DoDSF(prefix+"(",left-1,right,result);  
16:      if(left<right)  
17:        DoDSF(prefix+")",left,right-1,result);  
18:       return;  
19:    }  
20:  }  

Valid Parentheses

Problem:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Analysis:
Use stack and hashmap. Stack makes sure there is always "(" in front of ")", otherwise the string is not valid.

看了几天简单的算法看不懂。昨天找到一种笨方法，就是照着打，估计多打几遍就好了。

Solution:

1:  public class Solution {  
2:    public boolean isValid(String s) {  
3:      char[] chars=s.toCharArray();  
4:      HashMap<Character, Character> map=new HashMap<Character,Character>();  
5:      map.put('(', ')');  
6:          map.put('[', ']');  
7:         map.put('{', '}');  
8:         Stack<Character> stack = new Stack<Character>();  
9:         for(Character c: chars)  
10:         {  
11:           if(map.keySet().contains(c))  
12:            stack.push(c);  
13:           else if(map.values().contains(c))  
14:           {  
15:             if(!stack.isEmpty()&&map.get(stack.peek())==c)  
16:               stack.pop();  
17:             else   
18:             return false;  
19:           }  
20:         }  
21:         return stack.isEmpty();  
22:    }  
23:  }  

Longest Common Prefix

Problem:
Write a function to find the longest common prefix string amongst an array of strings.

Analysis:
Starting from the first char of the first string comparing with the rest. Leetocde 出问题了，strs.length()通不过。

Solution:

1:  public class Solution {  
2:    public String longestCommonPrefix(String[] strs) {  
3:      if(strs.length()==0)  
4:       return "";  
5:      if(strs==null)  
6:       return null;  
7:      String str0=strs[0];   
8:      for(int prefixLen=0;prefixLen<str0.length;prefixLen++)  
9:      {  
10:        char c=str0.charAt(prefixLen);  
11:        for(int j=1;j<strs.length();j++)  
12:        {  
13:          if(strs[j].length()<=prefixLen||strs[j].charAt(prefixLen)!=c)  
14:           return str0.substring(0,prefixLen);  
15:        }  
16:      }  
17:      return str0;  
18:    }  
19:  }  

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.

Analysis:

Check: http://stevekrenzel.com/articles/longest-palnidrome

Solution:

1:  public class Solution {  
2:    public String longestPalindrome(String s) {  
3:      if(s==null)  
4:      return null;  
5:      if(s.length()==1)  
6:      return s;  
7:      String result="";  
8:      for(int i=0;i<s.length();i++)  
9:      {  
10:       String temp1=getPalindrome(s,i,i);  
11:       if(temp1.length()>=result.length())  
12:       {  
13:         result=temp1;  
14:       }  
15:       String temp2=getPalindrome(s,i,i+1);  
16:        if(temp2.length()>=result.length())  
17:       {  
18:         result=temp2;  
19:       }  
20:      }  
21:      return result;  
22:    }  
23:    private String getPalindrome(String s, int begin, int end)  
24:    {  
25:      while(begin>=0&&end<s.length()&&s.charAt(begin)==s.charAt(end))  
26:      {  
27:        begin--;  
28:        end++;  
29:      }  
30:      return s.substring(begin+1,end);  
31:    }  
32:  }  

ZigZag Conversion

Problem:

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Analysis:
For the first and the last rows, the period between tow items is 2nRow-2(Step). For other rows, the period changes after every step. The first period is 2(nRows-1-rowIndex)(Step1), the second period is Step-Step1. 

Solution:

1:  public class Solution {  
2:    public String convert(String s, int nRows) {  
3:      if(nRows==1)  
4:       return s;  
5:      StringBuilder sb=new StringBuilder();   
6:      int step=2*nRows-2;//the period on the first and the last rows  
7:      for(int i=0;i<nRows;i++)  
8:      {  
9:        if(i==0 || i==nRows-1)//first row or last row  
10:        {  
11:         for(int j=i;j<s.length();j+=step)  
12:         {  
13:           sb.append(s.charAt(j));  
14:         }  
15:        }  
16:        else  
17:        {  
18:          int j=i;  
19:          int substep=2*(nRows-1-i);  
20:          while(j<s.length())  
21:          {  
22:            sb.append(s.charAt(j));  
23:            j+=substep;  
24:            substep=step-substep;    
25:          }  
26:        }  
27:      }  
28:      return sb.toString();  
29:    }  
30:  }