亚麻Onsite

[quote]害群之蚂蚁 发表于 2019-5-14 05:30

1. public class Coin_Word_Backtracking {
   
2.     public boolean find(String[] coins ...[/quote]
4. 嗯，我也感觉第二轮用backtrack毕竟靠谱。下面是我写的，大概看了一下，似乎思路差不多？
   
5. 
   
6. [code]  public boolean formLetter(char[][] list, String word) {
   
7.     // for every char character from A to Z, create a Set to store all the indices of coins where a char exists in the list
   
8.     ArrayList<Set<Integer>> coinsForletter = new ArrayList<>();
   
9.     for (int i = 0; i < 26; i++) {
   
10.       coinsForletter.add(i, new HashSet<>());
    
11.     }
    
12.     for (int i = 0; i < list.length; i++) {
    
13.       coinsForletter.get(list[i][0] - 'A').add(i);
    
14.       coinsForletter.get(list[i][1] - 'A').add(i);
    
15.     }
    
16.     return backtrack(coinsForletter, word.toCharArray(), new HashSet<Integer>(),  0);
    
17.   }
    
18.   
    
19.   // visited: a set of indices of coins that have already used one side (so we cannot use the other side anymore
    
20.   private boolean backtrack(ArrayList<Set<Integer>> coinsForletter, char[] letters, Set<Integer> visited, int start) {
    
21.     if (start >= letters.length) return true;
    
22.    
    
23.     char c = letters[start];
    
24.     for (Integer coin : coinsForletter.get(c - 'A')) {
    
25.       if (!visited.contains(coin)) {
    
26.         visited.add(coin);
    
27.         // if can continue all the way to the end, then it means we can return true for index `start`
    
28.         if (backtrack(coinsForletter, letters, visited, start + 1)) return true;
    
29.         // if backtrack() returns false above, it means that path cannot go through, so we backtrack
    
30.         visited.remove(coin);
    
31.       }
    
32.     }
    
33.     return false;
    
34.   }

复制代码

补充内容 (2019-6-10 13:48):
这里假设所有字母都是大写字母。如果是任意unix code，那就换成Map<Character, Set<Integer>>就行了