Re: [閒聊] 每日leetcode
https://leetcode.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n
1415. The k-th Lexicographical String of All Happy Strings of Length n
一個好字串是由abc三種字元組成的字串，相鄰的字元不相同，求出長度為n的所有好字串
中，字典順序第k小的好字串是什麼。
思路:
1.用dfs窮舉所有合法字串組合，做適當的剪枝。
2.把好字串丟到一個Heap裡面。
3.最後pop出第k個好字串。
Java Code:
------------------------------------------------
class Solution {
private PriorityQueue<String> pq;
public String getHappyString(int n, int k) {
pq = new PriorityQueue<>();
dfs(n, "");
if (k > pq.size()) {
return "";
}
String res = "";
for (int i = 0; i < k; i++) {
res = pq.poll();
}
return res;
}
void dfs(int n, String curr) {
if (curr.length() > 1 && curr.charAt(curr.length() - 1) ==
curr.charAt(curr.length() - 2)) {
return;
}
if (curr.length() >= n) {
pq.add(curr);
return;
}
for (char ch = 'a'; ch <= 'c'; ch += 1) {
dfs(n, curr + ch);
}
}
}
------------------------------------------------
--
https://i.imgur.com/gEScv9s.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1739977299.A.AC1.html
討論串 (同標題文章)
完整討論串 (本文為第 1338 之 1552 篇)：