1 / 2
Oct 2012

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.

  • created

    Oct '12
  • last reply

    May '20
  • 1

    reply

  • 610

    views

  • 2

    users

7 years later

were you able to solve this problem. If yes can you please discuss the approach