leetcode word-break（Java）
Leetcode Word Break
package com.my.test.leco.dyncplanning import java.util.HashSet import java.util.Set /** * Topic: * word-break * * Description of the topic: * 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'. * * Chinese definition: * Combine the elements in the dict, you can reuse them, can you spell them into s * */ public class WordBreak { /** * What is dynamic planning? * Introduction to Algorithms This book introduces this algorithm in this way. Dynamic programming is similar to the method of divide and conquer. It solves the original problem by combining the solutions of subproblems. * Let's take a look at what is the divide and conquer method, and the difference between the two. The divide and conquer method divides the problem into sub-problems that are disjoint, recursively solves sub-problems, and then combines their solutions to find the original The solution to the problem. * In contrast to dynamic programming, dynamic programming applications overlap with sub-problems, that is, different sub-problems have common sub-sub-problems (the sub-problems are recursively divided into smaller sub-problems) . * In this case, the divide and conquer method will do a lot of unnecessary work, and he will solve the common sub-subject problems repeatedly. Dynamic programming solves only one sub-problem problem once, and saves its solution in a table, so that it does not need to be recalculated every time a sub-sub problem is solved, avoiding unnecessary calculation work. * * Application scenarios for dynamic planning: * Dynamic programming methods are generally used to solve optimization problems. There are many feasible solutions to this type of problem. Each solution has a value. We want to find a solution with the optimal value. We call this solution an optimal solution to the problem, not the optimal solution, because there may be more The solutions all reach the optimal value. * Our solution to dynamic programming problems is generally divided into four steps: * 1. Define a state, which is a structural feature of an optimal solution * 2, state recursion, get recursive formula * 3, to initialize * 4, return results * * Solution method: * The core of the dynamic programming algorithm is to remember the solutions that have been asked, and remember that there are two ways to solve them: * 1 top-down memo method. The target value is calculated and calculated and saved in the cache (available array). * 2 from the bottom up. The sub-question is calculated first, and then the parent problem is calculated by the sub-question. */ /** * wordBreak
* * Idea: * 1. Find if f(j) = s[0,j](j>=0) can be combined by elements in dict * 2. State recursion, find out whether s[0,i](i>j) can be combined by elements in dict, state transition equation: f(i) = f(j) && f(j+1, i ) (j