thảo luận Leetcode mỗi ngày

realhaidinh đã nói:

8 là ["good", "good", "best", "word"] chứ đâu phải ["word","good","best","word"]

Nhấp để mở rộng...

Hover đã nói:

Có permutation nào tạo ra được substring bắt đầu ở vị trí 8 đâu bro.

Nhấp để mở rộng...

public class Solution
{
    private List<string> permutationWords = new List<string>();
    public IList<int> FindSubstring(string s, string[] words)
    {
        var visitedIndex = new HashSet<int>();
        backTracking(words, visitedIndex, "");
        var result = new List<int>();
        foreach (var item in permutationWords)
        {
           for(int i = 0; i< s.Length - item.Length; i++)
           {
               if(s.Substring(i, item.Length).Equals(item))
                result.Add(i);
           }
        }

        return result;
    }

    private void backTracking(string[] words, HashSet<int> visitedIndex, string path)
    {
        if (path.Length == words.Length * words[0].Length)
        {
            permutationWords.Add(new string(path));
            return;
        }

        for (int i = 0; i < words.Length; i++)
        {
            if (visitedIndex.Contains(i))
            {
                continue;
            }

            path += words[i];
            visitedIndex.Add(i);
            backTracking(words, visitedIndex, path);
            visitedIndex.Remove(i);
            path = path.Substring(0, path.Length - words[i].Length);
        }
    }
}

freedom.9 đã nói:

Thank fence, đúng ngáo À mình nhầm. Update lại mình failed ở test case này
https://leetcode.com/problems/substring-with-concatenation-of-all-words/
"wordgoodgoodgoodbestword" ["word","good","best","good"]
Output của mình ra là 8 do nó xài string permutation good good best word. Mà test case của Leetcode nó ra bài này là []
Code của mình

Spoiler: C#

C#:

public class Solution
{
    private List<string> permutationWords = new List<string>();
    public IList<int> FindSubstring(string s, string[] words)
    {
        var visitedIndex = new HashSet<int>();
        backTracking(words, visitedIndex, "");
        var result = new List<int>();
        foreach (var item in permutationWords)
        {
           for(int i = 0; i< s.Length - item.Length; i++)
           {
               if(s.Substring(i, item.Length).Equals(item))
                result.Add(i);
           }
        }

        return result;
    }

    private void backTracking(string[] words, HashSet<int> visitedIndex, string path)
    {
        if (path.Length == words.Length * words[0].Length)
        {
            permutationWords.Add(new string(path));
            return;
        }

        for (int i = 0; i < words.Length; i++)
        {
            if (visitedIndex.Contains(i))
            {
                continue;
            }

            path += words[i];
            visitedIndex.Add(i);
            backTracking(words, visitedIndex, path);
            visitedIndex.Remove(i);
            path = path.Substring(0, path.Length - words[i].Length);
        }
    }
}

via theNEXTvoz for iPhone

Nhấp để mở rộng...

Hover đã nói:

Mình mới run thử test đó thấy nó như này mà nhỉ.
Expected
[8]

Nhấp để mở rộng...

freedom.9 đã nói:

Thank fence, chắc mình bị ngáo cmnr mới ktra lại thì output của mình ra [] và expected là 8. Mình đọc lộn ngược.
Code mình có bug nên ko pass

Nhấp để mở rộng...

if (w2i.size() == 1){
            string tmp = "";
            for (auto word : words) tmp += word;
            int p = s.find(tmp, 0);
            while (p != string::npos){
                res.emplace_back(p);
                p = s.find(tmp, p + 1);
            }
            return res;
        }

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, vector<int>> w2i;
        int ns = s.size(), nw = words.size(), len = words[0].size();
        for (int i = 0; i < nw; ++i) w2i[words[i]].emplace_back(i);
        vector<int> res;
        if (w2i.size() == 1){
            string tmp = "";
            for (auto word : words) tmp += word;
            int p = s.find(tmp, 0);
            while (p != string::npos){
                res.emplace_back(p);
                p = s.find(tmp, p + 1);
            }
            return res;
        }
        
        bitset<5000> bm;
        vector<vector<bool>> visited(ns + 1, vector<bool>(nw, false));
        function<void(int)> solve = [&](int i) {
            int cnt = bm.count();
            if (i >= 0 &&  cnt == nw) {
                res.emplace_back(i);
                return;
            }
            int tmp = cnt;
            if (i < len || visited[i][cnt]) return;
            
            visited[i][cnt] = true; // mark as visited
            string word = s.substr(i - len, len);
            if (w2i.count(word)){
                for (int j : w2i[word]){
                    if (bm.test(j)) continue; // used
                    bm.set(j);
                    solve(i - len); // mark as used
                    break;
                }
            }
            bm.reset();
            solve(i - 1);
        };
        solve(ns);
        return res;
    }
};

afatnan đã nói:

Đọc tưởng dễ, nhưng hoá ra ko, làm toàn bị TLE
Phải có một đoạn này để khỏi bị TLE

C++:

if (w2i.size() == 1){
            string tmp = "";
            for (auto word : words) tmp += word;
            int p = s.find(tmp, 0);
            while (p != string::npos){
                res.emplace_back(p);
                p = s.find(tmp, p + 1);
            }
            return res;
        }

Spoiler: C++

C++:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, vector<int>> w2i;
        int ns = s.size(), nw = words.size(), len = words[0].size();
        for (int i = 0; i < nw; ++i) w2i[words[i]].emplace_back(i);
        vector<int> res;
        if (w2i.size() == 1){
            string tmp = "";
            for (auto word : words) tmp += word;
            int p = s.find(tmp, 0);
            while (p != string::npos){
                res.emplace_back(p);
                p = s.find(tmp, p + 1);
            }
            return res;
        }
       
        bitset<5000> bm;
        vector<vector<bool>> visited(ns + 1, vector<bool>(nw, false));
        function<void(int)> solve = [&](int i) {
            int cnt = bm.count();
            if (i >= 0 &&  cnt == nw) {
                res.emplace_back(i);
                return;
            }
            int tmp = cnt;
            if (i < len || visited[i][cnt]) return;
           
            visited[i][cnt] = true; // mark as visited
            string word = s.substr(i - len, len);
            if (w2i.count(word)){
                for (int j : w2i[word]){
                    if (bm.test(j)) continue; // used
                    bm.set(j);
                    solve(i - len); // mark as used
                    break;
                }
            }
            bm.reset();
            solve(i - 1);
        };
        solve(ns);
        return res;
    }
};

Nhấp để mở rộng...

Hover đã nói:

Nhìn code C++ không hiểu gì

Nhấp để mở rộng...

afatnan đã nói:

Ý tưởng cái mình code khá đơn gian, trong cái words thì lưu lại tất cả index của từng vào một hash. Mình sẽ có một bitmask để đánh dấu vị trí của từ nào trong words đã được sử dụng.

Nhấp để mở rộng...

afatnan đã nói:

Ý tưởng cái mình code khá đơn gian, trong cái words thì lưu lại tất cả index của từng vào một hash. Mình sẽ có một bitmask để đánh dấu vị trí của từ nào trong words đã được sử dụng. Dùng string thay cho bitset cũng được, bitset.test(i) xem vị trí này là 1 hay không, biset.set(i) set vị trí này là 1.

Nhấp để mở rộng...

freedom.9 đã nói:

Thực ra là do mình nghĩ phức tạp quá thôi fence haha.
Xài 1 cái dictionary để đếm từ, xong rồi ở mỗi vị trí từ 0 tới sLength - wordCounts* wordsLength
Khi gặp 1 từ thì giảm cái dictionary trong đó xuống cho tới khi xài hết dict thì thôi. Nếu xài hết thì thêm kết quả vô list trả về.

Overthinking quá cũng ko hay kaka, ý tưởng thì đơn giản vãi ra mà mình cứ sticks vào viết backtracking để build cái permutations, toang hoác.

Nhấp để mở rộng...

• Có khi lệch luôn chữ thứ 2 rồi vẫn đi so sánh tiếp các permutation tương tự có 2 chữ đó.
• Ngoài ra lệch chữ thứ 2 nhưng việc sinh permutation vẫn yêu cầu phải concat chữ thứ 3 thứ 4. Có khi cái permutation này không match bất kỳ chỗ nào.
• Trong xử lý của thím có đoạn substring ra để compare tốc độ chậm hơn nhiều so với iterate 2 index để so sánh trực tiếp.

NahSama đã nói:

Priority Queue

Đếm tần số xuất hiện mỗi chữ cái. Dùng PQ để lưu trữ tần số xuất hiện cao nhất đến thấp nhất, mỗi lần append vào String mới sẽ append chữ cái có tần số xuất hiện cao nhất (trừ 1 sau mỗi lần). Nếu 2 chữ cái kế nhau bằng nhau thì append bằng chữ cái có tần số cao thứ hai.

PQ size = 26 -> heapify O(log(26)) = O(1)

TC & SC: O(s.length)

Spoiler: 230823

Java:

class Solution {
    public String reorganizeString(String s) {
        char[] c = s.toCharArray();
        int[] cnt = new int[26];
        for (char i : c) {
            cnt[i - 'a']++;
        }

        Queue<Character> pq = new PriorityQueue<>((a, b) -> {
            return -(cnt[a - 'a'] - cnt[b - 'a']);
        });

        for (int i = 0; i < 26; i++) {
            pq.add((char) (i + 'a'));
        }


        StringBuilder sb = new StringBuilder();
        while(sb.length() < c.length) {
            char temp = pq.poll();
            if (sb.length() > 0 && sb.charAt(sb.length() - 1) == temp) {
                char temp2 = pq.poll();
                if (cnt[temp2 - 'a'] == 0) return "";
                sb.append(temp2);
                cnt[temp2 - 'a']--;
                pq.add(temp2);         
            } else {
                if (cnt[temp - 'a'] == 0) return "";
                sb.append(temp);
                cnt[temp - 'a']--;
            }
            pq.add(temp);
        }

        return sb.toString();
    }
}

Nhấp để mở rộng...

Hover đã nói:

Thím build toàn bộ permutation rồi compare là rất phí:

• Có khi lệch luôn chữ thứ 2 rồi vẫn đi so sánh tiếp các permutation tương tự có 2 chữ đó.
• Ngoài ra lệch chữ thứ 2 nhưng việc sinh permutation vẫn yêu cầu phải concat chữ thứ 3 thứ 4. Có khi cái permutation này không match bất kỳ chỗ nào.
• Trong xử lý của thím có đoạn substring ra để compare tốc độ chậm hơn nhiều so với iterate 2 index để so sánh trực tiếp.

Đoạn build permutation thím cũng làm chưa ổn lắm: dùng map visited là cách hơi chậm, ngoài ra việc concat và substring liên tục không tốt bằng chỉ concat ở bước cuối cùng (dùng mảng index dạng [0,3,2,1,4] để lưu permutation hiện tại sẽ tốt hơn).

Nhấp để mở rộng...

freedom.9 đã nói:

Quá chuẩn, thank fence. Mình biết nó sai rồi nên chưa tìm cách optimize thêm, mà đoạn visited đúng là phí thật. Nếu xài hashmap thì có thể xài để kiểm tra visited index luôn nhỉ

via theNEXTvoz for iPhone

Nhấp để mở rộng...

Konstante đã nói:

Cách này vừa hay vừa rất trực giác.

Tính chất duy nhất cần thiết cho việc tồn tại một hoán vị như vậy chính là tần suất của mỗi chữ cái. Hơn nữa có thể chứng minh được là nếu tồn tại một hoán vị thỏa mãn đề bài, mà phần tử ngoài cùng bên trái (hoặc bên phải) là một phần tử với tần suất k, thì cũng có thể xây dựng một hoán vị thỏa mãn đề bài mà phần tử ngoài cùng bên trái (tương ứng bên phải) là một phần tử với tần suất k' >= k.

Do vậy thuật toán này xây dựng được một hoán vị "tối ưu" (có thể có nhiều hoán vị "tối ưu" khác nhau), theo nghĩa là nếu không xây dựng được, thì không tồn tại hoán vị nào thỏa mãn đề bài.

Nhấp để mở rộng...

Hover đã nói:

Ý mình không phải thế. Thím đọc thêm thử method 1 (chỉ cần đọc trang 7) trong này nhé, cài đơn giản nhất có thể làm như vậy, không cần phải check cái nào đã visited:
https://sedgewick.io/wp-content/uploads/2022/03/2002PermGeneration.pdf
Còn tối ưu hơn thì là dùng thuật toán của Heap để sinh, mỗi một phát swap là ra một permutation mới luôn.
https://en.wikipedia.org/wiki/Heap's_algorithm

Nhấp để mở rộng...

freedom.9 đã nói:

Sao mình chưa thấy cái thuật toán heap này ở đâu nhỉ, ví dụ bài này
Tụi nó cũng chỉ xài backtracking
https://leetcode.com/problems/permutations

Nhấp để mở rộng...

Hover đã nói:

Thuật toán Heap cũng backtracking nhưng số thao tác của nó là tối thiểu thím ạ. Thím thử cài xem.

Nhấp để mở rộng...

freedom.9 đã nói:

Sao mình chưa thấy cái thuật toán heap này ở đâu nhỉ, ví dụ bài này
Tụi nó cũng chỉ xài backtracking
https://leetcode.com/problems/permutations

Nhấp để mở rộng...

Hover đã nói:

Nó là greedy mà thím, nên câu cuối của thím chuẩn rồi. Tuy nhiên có nhiều cách xây khác, và bài này thì có cách xây đơn giản hơn cách mà thím quote.

Nhấp để mở rộng...