Word Break 2 solution

Word Break 2 solution

  July 11, 2018    

---

Problem:
make sentence from a sequence of chars from given dictionary.

Idea is to find every matching substring in dictionary try to match rest of substring , if found then print.

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
    static boolean found=false;
     public static boolean dictionary(String a[],String b)
     {
         for(int i=0;i<a.length;++i)
            if(a[i].compareTo(b)==0)
            return true;
            return false;
     }
  public static void fn(String a[],int n,String b,int start,String res)
  {
      int m=b.length();
      if(start>=m)
      return;
      for(int i=start+1;i<=m;++i)
      {
          if(dictionary(a,b.substring(start,i)))
          {
              if(i==m)
              {System.out.print("("+res+b.substring(start,i)+")");
                  found=true;
              }
              else
               {
                   fn(a,n,b,i,res+b.substring(start,i)+" ");
                   
               }
          }
      }
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    found=false;
    int n=ab.nextInt();
    String arr[]=new String[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.next();
    fn(arr,n,ab.next(),0,"");
    if(!found)
    System.out.print("Empty");
    System.out.println();
}
}
}