Snap面经题目: Word Combinations

0002505492

题目:

一个INPUT STRING ARRAY1 比如CAT, DOG,一个INPUT STRING ARRAY 2, 比如GAT, DOC, CD, GOAT, BAD, COOL.
要求第一个INPUT ARRAY的字母必须全部用,而且每个字母只能用一次,求其能组合成的INPUT STRING ARRAY2里的单词组合
比如上面这个例子,返回值会是{{GAT, DOC},{CD, GOAT}}

思路:使用DFS,非常简单。

代码:

import java.util.*;
public class Solution {
	public static void main(String[] args)
	{
		String[] input1 = {"CAT", "DOG"};
		String[] input2 = {"GAT", "DOC", "CD", "GOAT", "BAD", "COOL"};
		List<List> ans = wordCombinations(input1, input2);
		for(List l: ans)
		{
			System.out.println("********");
			for(String s: l) System.out.print(s + " ");
			System.out.println("");
		}
	}

	private static List<List> wordCombinations(String[] input1, String[] input2) {
		// TODO Auto-generated method stub
		int[] count = new int[26];
		int sum = 0;
		for(String s: input1)
		{
			for(char c: s.toCharArray()) 
			{
				count++;
				sum++;
			}
		}
		List<List> ans = new ArrayList<>();
		DFS(0, 0, sum, count, input2, new ArrayList(), ans);
		return ans;
	}

	private static void DFS(int index, int currentSum, int sum, int[] count, String[] input, ArrayList list,
			List<List> ans) {
		// TODO Auto-generated method stub
		if(currentSum == sum)
		{
			ans.add(new ArrayList(list));
			return;
		}
		for(int i = index; i < input.length; i++)
		{
			boolean flag = false;
			for(char c : input[i].toCharArray()) 
			{
				count--;
				currentSum++;
				if(count < 0) flag = true;
			}
			if(!flag)
			{
				list.add(input[i]);
				DFS(i+1, currentSum, sum, count, input, list, ans);
				list.remove(list.size() - 1);
			}
			for(char c : input[i].toCharArray()) 
			{
				count++;
				currentSum--;
			}
		}
	}
	
}

Output:

********
GAT DOC
********
CD GOAT

744total visits,1visits today