- #刷题
- #高频题
求问这道算法题该怎么解

5583
Given a collection of blocks with letters on them, and a target word, determine if the blocks can form the target word
(B,A),(A,B),(X,Y),(A,B): "BABY" => yes
(B,A),(A,B),(L,E),(A,B): "ABLE" => no (since L and E are on the same block).
我想到的就是可以用dfs来找某个与target word对应的切入点,然后看是否能匹配整个word, 以下是我的代码
[mw_shl_code=java,true]
class solutions {
public boolean solution(List<List<String>> wordList, String target) {
if (target.length() > wordList.size()) return false;
Map<String, Integer> hm = new HashMap<>();
for (char c : target.toCharArray()) {
hm.put(c + “”, hm.getOrDefault(c, 0) + 1);
}
return formWordPairsHelper(wordList, hm, target.length(), new HashSet<>());
}
public boolean formWordPairsHelper(List<List<String>> wordList, Map<String, Integer> hm, int count, Set<Integer> visited) {
if (visited.size() == wordList.size()) {
if (count == 0) return true;
return false;
}
for (int i = 0; i < wordList.size(); i++) {
for (String s : wordList.get(i)) {
if (!visited.contains(i) && hm.containsKey(s) && hm.get(s) > 0) {
hm.put(s, hm.get(s) - 1);
visited.add(i)
boolean res = formWordPairsHelper(wordList, hm, count - 1, visited);
if (res) return true;
visited.remove(i);
hm.put(s, hm.get(s) + 1);
}
}
}
return count == 0;
}
[/mw_shl_code]
还请大神看一看这样写对不对
(B,A),(A,B),(X,Y),(A,B): "BABY" => yes
(B,A),(A,B),(L,E),(A,B): "ABLE" => no (since L and E are on the same block).
我想到的就是可以用dfs来找某个与target word对应的切入点,然后看是否能匹配整个word, 以下是我的代码
[mw_shl_code=java,true]
class solutions {
public boolean solution(List<List<String>> wordList, String target) {
if (target.length() > wordList.size()) return false;
Map<String, Integer> hm = new HashMap<>();
for (char c : target.toCharArray()) {
hm.put(c + “”, hm.getOrDefault(c, 0) + 1);
}
return formWordPairsHelper(wordList, hm, target.length(), new HashSet<>());
}
public boolean formWordPairsHelper(List<List<String>> wordList, Map<String, Integer> hm, int count, Set<Integer> visited) {
if (visited.size() == wordList.size()) {
if (count == 0) return true;
return false;
}
for (int i = 0; i < wordList.size(); i++) {
for (String s : wordList.get(i)) {
if (!visited.contains(i) && hm.containsKey(s) && hm.get(s) > 0) {
hm.put(s, hm.get(s) - 1);
visited.add(i)
boolean res = formWordPairsHelper(wordList, hm, count - 1, visited);
if (res) return true;
visited.remove(i);
hm.put(s, hm.get(s) + 1);
}
}
}
return count == 0;
}
[/mw_shl_code]
还请大神看一看这样写对不对
3条回复
热度排序