[LeetCode] Word Break

Problem

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

First scan, mark every possible string section.

Second scan, dynamic programming,  for every string 0~i, it is a valid break-able string only if its previous string 0~j and new part j+1~ i are both valid words in the dictionary.

 


class Solution {  
 public:  
      bool wordBreak(std::string s, std::unordered_set<std::string> &dict) {  
           int n = s.size();  
           if(n==0||dict.size()==0)  
                return false;  
           std::vector<std::vector<bool>> map(n+1, std::vector<bool>(n+1, false));  
           map[0][0] = true;  
           std::vector<bool> memo(n+1, false);  
           memo[0] = true;  
           std::string tmp;  
           for(int i=0; i<n; i++)  
           {  
                for(int j=i; j<n; j++)  
                {  
                     tmp = s.substr(i, j-i+1);  
                     if(dict.find(tmp)!=dict.end())  
                          map[i+1][j+1]=true;  
                }  
           }  
           for(int i=0; i<n; i++)  
           {  
                for(int j=0; j<=i; j++)  
                {  
                     if(memo[j+1-1]&&map[j+1][i+1])  
                          memo[i+1] = true;  
                }  
           }  
           return memo[n];  
      }  
 };  

[LeetCode] Valid Number

Link : Valid Number

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.

Analysis:
Test case is quite important.
To make clear what if input is NULL, '\0', or "    "(only space).
exponential part is quite important.

I tried several times, and there is always some case that I didn't expect.
This is intentionally a vague problem. So ask for details from interviewers, if possible.

[LeetCode] Longest Palindromic Substring

Link : Longest Palindromic Substring

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:

First thought is brute force. For every kind selection of start point and end point, there are totally O(N*N) and each palindrome recognition is O(N). And total time complexity is O(N^3). Test proved it's too slow.

Second try. Because Palindrome has special property, symmetric. If a long string is a Palindrome, the sub-string in its center has to be a sub-string. Or in another way, if its sub-string in the middle is not a palindrome, the large one cannot be, thus avoiding a lot of unnecessary comparison.