CareerCup

// for simplicity assume all characters are in lower case
public class FormWordsFromChemistryPeriodicTable {
	
	public static List<String> findWords (String[] dictionary, HashSet<String> periodicTableElements) {

		List<String> words = new LinkedList<String>();
		
		if(dictionary == null || periodicTableElements == null 
				|| periodicTableElements.isEmpty() || dictionary.length ==0)
			return words;
		
		for (int i = 0; i < dictionary.length; i++) {
			
			boolean flag = true;
			
			for (int j = 0; j < dictionary[i].length(); j++) {
				// if current letter is an element symbol, continue loop; else check its neighbhours 
				if (! periodicTableElements.contains("" + dictionary[i].charAt(j))) {				
					
					// if current letter is not an element symbol 
					// check if the prev letter + this letter is a symbol, 
					// else; check if this letter + next letter is a symbol
					if ( ! (
							(j != 0) && 
							periodicTableElements.contains("" + dictionary[i].charAt(j-1) + dictionary[i].charAt(j)))) {
						
						if ((j == dictionary[i].length()-1) || 
								! periodicTableElements.contains("" + dictionary[i].charAt(j) + dictionary[i].charAt(j+1))) {
							flag = false;
							break;
						}	
						
						j=j+1;
					}
				}
			}
			
			if(flag == true) {
				words.add(dictionary[i]);
			}
		}
		
		return words;
		
	}
	
	public static void main(String[] args) {
		String[] dictionary = {"ark","sick", "arc", "arch", "arche"};
        HashSet<String> periodicTableElements = new HashSet<String>();
        periodicTableElements.add("ar");
        periodicTableElements.add("k");
        periodicTableElements.add("si");
        periodicTableElements.add("c");
        periodicTableElements.add("ch");
        System.out.println(findWords (dictionary, periodicTableElements));
	}

}

Hash all the symbols from Chemistry Periodic table. For any given words, use DP to test whether the word can be formed by the hash table. dp[i][j]: whether the sub sequence word[0,...,i-1] can be created.
dp[i][j] = dp[i][j-1] word[i] in the hash table or
dp[i][j-2] word[i-1,i] in the hash table.

This is similar to reconstruct a sentence without space between words.
This one is easier, since we know the length of a word is at most 3.

Using array to record the computed values, the algorithm can be done in O(n)

We can do this by hashing all the words of periodic table,
for comparing [AKBaBr] we can make a bool array(exist) of size 6 , with each exist[i] denotes word from 0 to i exist or not.

Suppose at time t, we arrive at [true,true,false,true,unknown,unknown] , now to fill exist[4] check (exist[3]==true and word[4] is in hash table) Or (exist[2]==true and word[4,5] is in hash table.) ... as both are false so exist[5]=false.

for exist[6] check (exist[4]==true and word[5] is in hash table) Or (exist[3]==true and word[5,6] is in hash table.) as 2nd condition is true .. therefore exist[6] is also true. return(exist[6]);