148 - Anagram checker

[Karim El Sheikh]

I get TLE. Am I missing some ideas? I do count the remaining Digits like what was said here.
My code is in Java, I also have code in C++ that also TLE. Any ideas?

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;


public class Main {

	static int chars[] = new int[26];
	static boolean used[] = new boolean[2000];
	static int remaining[][] = new int[2000][26];
	static String words[] = new String[2000];
	static int goals[][] = new int[2000][26];
	static String phrases[] = new String[2000];
	static String oPhrases[] = new String[2000];
	static int n, p;
	static PrintWriter out = new PrintWriter(System.out);
	static int goal;
 	public static void removeChars(int  index) {
		for(int i = 0; i < words[index].length(); i++)
			chars[words[index].charAt(i)-'A']--;
	}
	public static void addChars(int index) {
		for(int i = 0; i < words[index].length(); i++)
			chars[words[index].charAt(i)-'A']++;
	}
	public static void solution(int index) {
		boolean possible = true;
		for(int i = 0; i < 26; i++) {
			if(chars[i]!=goals[goal][i]) {
				possible = false;
			}
		}
		if(possible) {
			StringTokenizer st = new StringTokenizer(oPhrases[goal]);
			boolean[]match = new boolean[n];
			boolean matched = true;
			while(st.hasMoreTokens()&&matched) {
				String s = st.nextToken();
				matched = false;
				for(int j = 0; j < n; j++) {
					if(!match[j]&&used[j]&&s.equals(words[j])) {
						match[j] = true;
						matched = true;
						break;
					}
				}
			}
			boolean noDifference = true;
			for(int i = 0; i < n; i++) {
				if(used[i]&&!match[i]) {
					noDifference = false;
					break;
				}
			}
			if(noDifference)
				return;
			out.print(oPhrases[goal] + " =");
			for(int i = 0; i < n; i++) {
				if(used[i])
					out.print(" "+words[i]);
			}
			out.println();
			return;
		}
		if(index == n)
			return;
		for(int i = 0; i < 26; i++) {
			if(remaining[index][i]+chars[i]<goals[goal][i])
				return;
		}
		solution(index  + 1);
		addChars(index);
		used[index] = true;
		solution(index + 1);
		used[index] = false;
		removeChars(index);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = 0; p = 0;
		String s = br.readLine();
		while(s.charAt(0)!='#') {
			words[n++] = s;
			s = br.readLine();
		}
		String ss = br.readLine();
		s = ss.replaceAll("\\s","");
		while(ss.charAt(0)!='#') {
			phrases[p] = s;
			oPhrases[p] = ss;
			for(int i = 0; i < s.length(); i++) {
				goals[p][s.charAt(i)-'A']++;
			}
			p++;
			ss = br.readLine();
			s = ss.replaceAll("\\s","");
		}
		for(int j = 0; j < words[n-1].length(); j++) {
			remaining[n-1][words[n-1].charAt(j)-'A']++;
		}
		for(int i = n - 2; i >= 0; i--) {
			for(int j = 0; j < words[i].length(); j++)
				remaining[i][words[i].charAt(j)-'A']++;
			for(int j = 0; j < 26; j++) {
				remaining[i][j]+=remaining[i+1][j];
			}			
		}
		for(int i = 0; i < p; i++) {
			goal = i;
			solution(0);
		}
		out.flush();
		

	}

}

[Karim El Sheikh]

I managed to solved it, the major modification was while adding the count of the individual characters, each time I check if this character's count is more than than its count in the phrase, and prune if found so.