CONY的世界

139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

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

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

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

也是一題dp，但是因為我想不到怎麼拆解所以最後還是看討論

基本上就是  i 是否有word 是由所有之前可構成的word ＋ 剩下的是否是word 來決定

ex. leetcode 是否是word  ＝ leet 是否是word字 ＆＆ 剩下的word 是否是word構成 

                       所以反例就是  leetcod ＝ leet 是單字, but 剩下的 cod 不是word 所以為否

                                     或者                    lee 不是單字 （後面就也不用看了）

 這樣由小拼圖街成大拼圖完成，本來想得太複雜，還想用 Floyd 但是其實不用，這樣找不到所謂的規則性

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet();
        for(String word: wordDict)
            set.add(word);
        boolean[] word_list = new boolean[s.length()+1];
        word_list[0] = true;
        for(int i=1; i<= s.length(); i++){
            for(int j=0; j < i; j++){
                if(word_list[j] && set.contains(s.substring(j,i))) {
                    word_list[i] = true;
                    break;
                }
            }
        }
        return word_list[s.length()];
    }
}

238. Product of Array Except Self 

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length, right=1;
        int[] res = new int[len];
        res[0] = 1;
        for(int index=1; index < len; index++)
            res[index] = res[index-1] * nums[index-1];
        
        for(int index = len-1; index>=0; index--){
            res[index] *= right;
            right *= nums[index];
        }
        return res;
    }
}