HI,
I am getting WA in ACMAKER. I tried for all the testcases I can think of, but dont know where I am going wrong. Can someone please give me some testcases where the result is wrong?
I am using dp. I first truncate insignificant words and then proceed using dp. Complete code is given below:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class ACMAKER {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int insignificantWordLength = Integer.parseInt(br.readLine());
while(insignificantWordLength > 0){
String[] insignificantWords = new String[insignificantWordLength];
for(int i=0;i<insignificantWordLength;i++){
insignificantWords[i] = br.readLine();
}
String inputStr = br.readLine();
while(!inputStr.equals("LAST CASE")){
StringTokenizer stz = new StringTokenizer(inputStr);
String originalAbbr = stz.nextToken();
String abbr = originalAbbr.toLowerCase();
String validWord = "";
ArrayList<Integer> wordMarker = new ArrayList<Integer>();
Map<Integer, Integer> wordLengthDict = new HashMap<Integer, Integer>();
int wordCount = 0;
int totalWordLength = 0;
while(stz.hasMoreTokens()){
String s = stz.nextToken();
if(!HasWord(insignificantWords, s)){
int currentWordLength = s.length();
validWord += s;
markWord(wordMarker, wordCount, currentWordLength);
totalWordLength += currentWordLength;
wordLengthDict.put(wordCount,totalWordLength);
wordCount++;
}
}
//System.out.println(validWord);
//System.out.println(wordMarker.toString());
int abbrCount = getAbbrCount(validWord.toCharArray(), abbr.toCharArray(), wordMarker, wordLengthDict);
if(abbrCount == 0){
System.out.println(originalAbbr+" is not a valid abbreviation");
}
else{
System.out.println(originalAbbr+" can be formed in "+abbrCount+" ways");
}
inputStr = br.readLine();
}
insignificantWordLength = Integer.parseInt(br.readLine());
}
}
private static boolean HasWord(String[] strArray, String word){
for(String s : strArray){
if(s.equals(word)){
return true;
}
}
return false;
}
private static void markWord(ArrayList<Integer> wordMarker, int n, int length){
for(int i=0;i<length;i++){
wordMarker.add(n);
}
}
private static int getAbbrCount(char[] sentence, char[] abbr, ArrayList<Integer> wordMarker, Map<Integer, Integer> wordLengthDict){
int sentenceLength = sentence.length;
int abbrLength = abbr.length;
int[][] dp = new int[abbrLength+1][sentenceLength+1];
for(int i=0;i<abbrLength+1;i++) dp[i][0] = 0;
for(int i=0;i<sentenceLength+1;i++) dp[0][i] = 0;
for(int i=1;i<abbrLength+1;i++){
for(int j=1;j<sentenceLength+1;j++){
if(IsWordStart(j-1, wordMarker)){
if(i == 1){
if(abbr[i-1] == sentence[j-1] && IsAbbrWordMatch(i-1, j-1, wordMarker, abbrLength)) dp[i][j] = 1;
else dp[i][j] = 0;
}
else{
if(abbr[i-1] == sentence[j-1] && IsAbbrWordMatch(i-1, j-1, wordMarker, abbrLength)) dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
else dp[i][j] = 0;
}
}
else{
if(i == 1){
if(abbr[i-1] == sentence[j-1] && IsAbbrWordMatch(i-1, j-1, wordMarker, abbrLength)) dp[i][j] = 1 + dp[i][j-1];
else dp[i][j] = dp[i][j-1];
}
else{
int currentWord = wordMarker.get(j-1);
if(abbr[i-1] == sentence[j-1] && IsAbbrWordMatch(i-1, j-1, wordMarker, abbrLength)) {
dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
if(currentWord > 0){
dp[i][j] += dp[i-1][wordLengthDict.get(currentWord-1)];
}
}
else{
dp[i][j] = dp[i][j-1];
}
}
}
}
}
/*for(int i=0;i<abbrLength+1;i++){
for(int j=0;j<sentenceLength+1;j++){
System.out.print(dp[i][j]);
}
System.out.println();
}*/
return dp[abbrLength][sentenceLength];
}
private static boolean IsAbbrWordMatch(int i, int j, ArrayList<Integer> wordMarker, int abbrLength){
int wordJ = wordMarker.get(j);
boolean condn1 = ((abbrLength - 1) - i) >= (wordMarker.get(wordMarker.size()-1) - wordJ);
boolean condn2 = wordJ <= i;
return condn1 && condn2;
}
private static boolean IsWordStart(int i,ArrayList<Integer> wordMarker){
return (i == 0 || wordMarker.get(i) - wordMarker.get(i-1) == 1);
}
}
Thanks in advance.