JavaScript|LeetCode|动态规划/BFS|139. 单词拆分

法1：动态规划
想法：

1. 字符串 s 是背包
2. 单词列表 wordDict 中的单词是物品
3. 物品可重复放入背包
4. 数组dp：

• dp[i]表示：s 中以 s[0] 开头的 i 长度的子串 代表的 背包，是否可正好被单词装满

/** 
* @param {string} s 
* @param {string[]} wordDict 
* @return {boolean} 
*/
var wordBreak = function(s, wordDict) {    
    // 字符串s是背包    
    // 单词列表wordDict中的单词是物品    
    // 物品可重复放入背包
    
    // dp[i]表示：    
    // s中以s[0]开头的 i 长度的子串 代表的 背包，是否可正好被单词装满    
    var dp = [], i = 0, j = 0, exist = 0;
    
    for(i = 0; i <= s.length; i++) {        
        dp[i] = false;
        subs[i] = s.substr(0, i); // s中以s[0]开头，长度为i的子串    
    }
    
    // 空字符串一定可以被单词装满    
    // 相当于不分割字符串    
    // 为协调全部分割状态，故采取dp[0]为true的形式    
    // 只要剩余字符串可以被装满，则两者相与为true，可被装满    
    dp[0] = true; 
    
    for(i = 1; i <= s.length; i++) { // 对于各容量背包，即 s 中以s[0]开头的 i 长度的子串        
        for(j = 0; j < wordDict.length; j++) { // 对于wordDict中每个单词            
            if(i >= wordDict[j].length) { // 子串长度长于当前单词                
                // 寻找当前单词在子串中最后一次出现的位置
                exist = subs[i].lastIndexOf(wordDict[j]);                
                // 子串可容纳当前单词，且单词正好填充结尾位置                
                if(exist > -1 && exist + wordDict[j].length == i) {                     
                    dp[i] = dp[i - wordDict[j].length] || dp[i];                
                }            
            }        
        }       
    }    
    return dp[s.length];
};

法2：BFS
想法：

1. 将 s 作为根，与根的前几个字符相符合的单词作为边，剩余的子串作为孩子（根与孩子之间相差的字符所组成的词在wordDict中，则根与孩子的邻点关系成立）
2. 新的孩子作为新的根，找新根的孩子，最后可以到达 “” 叶子节点，则返回true，否则返回false

注：下面第一份代码是没有通过的！！原因：超时：应设置visited数组来标记哪个子串已经存在，则不重复访问

/** 
* @param {string} s 
* @param {string[]} wordDict 
* @return {boolean} 
*/
var wordBreak = function(s, wordDict) {    
    // BFS    
    // s为根，经过若干“单词”边，到""
    
    // arr保存每一层的节点，length保存每层节点的个数    
    var arr = [], length = 0, i = 0;    
    arr[0] = s; // 从根开始
    
    while(arr.length > 0) { // arr中还有节点        
        length = arr.length;        
        // 将当前层的每个节点的孩子（即下一层节点）加入arr        
        while(length > 0) { // 当前层还有节点            
            if(arr[0] == "") {                
                return true;            
            }            
            for(i = 0; i < wordDict.length; i++) {                
                if(arr[0].length < wordDict[i].length) {                    
                    continue;                
                }                
                else if(arr[0].indexOf(wordDict[i]) == 0) {
                    arr.push(arr[0].substr(wordDict[i].length)); // 剩下的子串是孩子                
                }            
            }               
            arr.shift();             
            length--;        
        }    
    }    
    return false;
};

优化
想法：

1. 设置visited数组，来保存已经访问过的节点
2. 保存子串，不如保存子串在 s 中的起点下标（终点即 s 末尾）

/** 
* @param {string} s 
* @param {string[]} wordDict 
* @return {boolean} 
*/
var wordBreak = function(s, wordDict) {    
    // BFS    
    // s为根，经过若干“单词”边，到""
    
    // arr保存每一层的节点，length保存每层节点的个数    
    var arr = [], length = 0, i = 0, subs = "", visited = [];    
    for(i = 0; i < s.length; i++) {        
        visited[i] = false;    
    }    
    arr[0] = 0; // 从根开始
    
    while(arr.length > 0) { // arr中还有节点        
        length = arr.length;        // 将当前层的每个节点的孩子（即下一层节点）加入arr        
        while(length > 0) { // 当前层还有节点            
            if(!visited[arr[0]]) { // 以arr[0]为起点的子串还未被访问                
                subs = s.substr(arr[0]);                
                if(wordDict.indexOf(subs) > -1) {                     
                    // 当前剩余串在wordDict中，直接返回true                    
                    return true;                
                }                
                for(i = 0; i < wordDict.length; i++) {                    
                    if(subs.length < wordDict[i].length) {                        
                        continue;                    
                    }                    
                    else if(subs.indexOf(wordDict[i]) == 0) {
                        // 将匹配完的单词部分从当前根中去除，记录子串的开始下标                        
                        arr.push(arr[0] + wordDict[i].length);                     
                    }                
                }                
                visited[arr[0]] = true; // 以arr[0]开始的子串已经访问过，避免重复访问            
            }            
            arr.shift();             
            length--;        
        }    
    }    
    return false;
};