登录
  • #刷题
  • #高频题

求问‌‌‍‍‌‍‍‌‍‌‌‍‌‍‍‍‌‌‌‌‍‌‍‌‌‍‌‌‌‍‌‍这道算法题该怎么解

tt198866
558
3
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]

还请大神看一看这样写对不对
3条回复
热度排序

发表回复