Doublets

Doublets.java

package main;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Doublets {
	
	public static boolean track(Object [] dict,List<String> output, int begin, int end) {
		
		for (int i = begin+1; i <= end; i++) {
			if (doublets((String)dict[begin], (String)dict[i])) {
				if (i == end ) {
					output.add((String)dict[i]);
					return true;
				} else {
					output.add((String)dict[i]);
					boolean test = track(dict, output, i, end);
					if (test)
						return test;
					
					else {
						// clear output
						while(!output.get(output.size()-1).equals(dict[i])) {
							output.remove(output.size()-1);
						}
						output.remove(output.size()-1);
					}
				}
			}
		}
		return false;
	}

	public static boolean doublets(String s1, String s2) {
		
		if (s1.length() != s2.length())
			return false;
		int c = 0;
		for (int i = 0; i < s1.length(); i++ ) {
			if (s1.charAt(i) != s2.charAt(i))
				c++;
			if (c > 1)
				return false;
		}
		if (c == 1) return true;
		return false;
	}
	
	public static void main(String[] args) {
		List<String> input = new LinkedList<String>();
		Scanner scan = new Scanner(System.in);
		boolean flag = false;
		while(scan.hasNextLine()) {
			String s = scan.nextLine();
			if (s.equals("")) {
				flag = true;
				continue;
			}
			if (!flag) {
				input.add(s);
			} else {
				List<String> output = new LinkedList<String>();
				String [] test = s.split(" ");
				int begin = input.indexOf(test[0]);
				int end = input.indexOf(test[1]);
				output.add(test[0]);
				if (track(input.toArray(),output,begin,end )) {
					for (String ss: output) {
						System.out.println(ss);
					}
					System.out.println();
				} else {
					System.out.println("No Solution\n");
				}
			}
			
		}
	}

}