package question;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Question139 {
 public static void main(String[] args) {
 //"leetcode"
 //["leet","code"]
 //"applepenapple"
 //["apple","pen"]
 String s="aaaaaaa";
 List<String> list = new LinkedList<>();
 list.add("aaaa");
 list.add("aaa");
 System.out.println(new Question139().wordBreak(s, list));
 }
 public boolean wordBreak(String s, List<String> wordDict) {
 int[][] dp = new int[s.length()][s.length()];
 for (int i = 0; i < dp.length; i++) {
 dp[i][i]=i;
 }
 for (int k = 0; k < s.length(); k++) {
 for (int i = 0, j=i+k; j < s.length(); i++, j++) {
 for (String s1 : wordDict) {
 if ((i==j&&s1.equals(s.substring(dp[i][j],j+1)))||(j>i&&s1.equals(s.substring(dp[i][j-1],j+1)))) {
 dp[i][j]=j+1;
 break;
 } else {
 if (j>i) dp[i][j]=dp[i][j-1];
 }
 }
 }
 }
 return dp[0][s.length()-1]==s.length();
 }
}