Snap面经题目: filter dictionary

0002505492

题目:

public List solution (char[] array, List dic) {}
输出由array中任意字符组合成的在字典里的所有String。

举个例子: char[] array = {‘A’, ‘B’, ‘C’, ‘A’}, List = {“A”,”AA”,”BA”};
输出: “A”, “AA”,”BA”;

解答:使用trie + DFS


import java.util.*;
class TrieNode
{
	TrieNode[] children;
	String word;
	
	public TrieNode()
	{
		children = new TrieNode[26];
	}
}
public class Solution {
	static TrieNode root;
	private static List filter(char[] array, List list) {
		// TODO Auto-generated method stub
		root = new TrieNode();
		buildTrie(root, list);
		int[] count = new int[26];
		for(char c: array) count++;
		List res = new ArrayList<>();
		DFS(root, count, res);
		return res;
	}

	private static void DFS(TrieNode root, int[] count, List res) {
		// TODO Auto-generated method stub
		if(root.word != null) res.add(root.word);
		for(int i = 0; i < 26; i++)
		{
			if(root.children[i] != null && count[i] > 0)
			{
				count[i]--;
				DFS(root.children[i], count, res);
				count[i]++;
			}
		}
	}

	private static void buildTrie(TrieNode root, List list) {
		// TODO Auto-generated method stub
		for(String s: list)
		{
			TrieNode t = root;
			for(int i = 0; i < s.length(); i++)
			{
				int k = s.charAt(i) - 'a';
				if(t.children[k] == null) t.children[k] = new TrieNode();
				t = t.children[k];
			}
			t.word = s;
		}
	}
	public static void main(String[] args)
	{
		char[] array = {'a', 'b', 'c', 'a'};
		List list= Arrays.asList("a", "aa", "ba", "aaac", "aba", "aba", "abbbb", "aabc", "abca");
		List ans = filter(array, list);
		for(String s: ans) System.out.println(s);
	}
}

<\pre>

输出:

a
aa
aabc
aba
abca
ba

375total visits,1visits today