Ex 6_4 判断序列是否由合法单词组成..._第六次作业

 package org.xiu68.ch06.ex6;

 import java.util.HashSet;

 import java.util.Set;

 //利用动态规划算法判断一个字符串是否由有效的单词组成，若是则输出单词序列,算法的运行时间不超过n的平方

 public class Ex6_4 {

     private static Set<String> wordSet;

     public static void main(String[] args) {

         // TODO Auto-generated method stub

         wordSet=new HashSet<>();

         wordSet.add("it");

         wordSet.add("was");

         wordSet.add("the");

         wordSet.add("algorithoms");

         wordSet.add("best");

         wordSet.add("is");

         wordSet.add("of");

         wordSet.add("times");

         wordSet.add("interesting");

         wordSet.add("good");

         String strs1=" itwasthebestoftimesgood";

         checkWord(strs1);     //true:it was the best of times good 

         String strs2=" algorithomsisinteresting";

         checkWord(strs2);     //true:algorithoms is interesting 

         String strs3=" thisisastring";

         checkWord(strs3);    //false:

     }

     public static void checkWord(String strs){

         boolean[] vi=new boolean[strs.length()];            //记录前i个字符组成的子串能否分割成有效的单词

         vi[0]=true;

         int[] index=new int[strs.length()];                  //记录以该下标为终点的合法单词的起始位置

         index[0]=-1;                                      //不能构成合法单词

         for(int i=1;i<=strs.length()-1;i++){              //判断前i+1个字符组成的子串能否分割成有效的单词

             for(int j=i-1;j>=0;j--){

                 String strTemp=strs.substring(j+1,i+1);

                 if(vi[j] && isAWord(strTemp)){

                     vi[i]=true;

                     index[i]=j+1;

                     break;

                 }

                 else{

                     vi[i]=false;

                     index[i]=-1;

                 }

             }

         }//外for

     //打印出单词序列

         System.out.print(vi[strs.length()-1]+":");

         if(vi[strs.length()-1]){

             String words="";

             int b=strs.length()-1;

             int a=index[b];

             while(a!=-1){

                 words=strs.substring(a,b+1)+" "+words;

                 b=a-1;

                 a=index[b];

             }

             System.out.println(words);

         }

     }

     //判断单词是否合法

     public static boolean isAWord(String str){

         if(wordSet.contains(str))

             return true;

         return false;

     }

 }