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

thuyduong2007 said:
Đồng ý với fen cái số 2, còn cái số 1 là bắt buộc mà. Nó mới sort theo lexicographical thôi mà, :big_smile:
Click to expand...
À đúng, vì fen dùng substr nên phải kiểm tra cái lenght chứ không sẽ bị lỗi, haha.
Ý mình là việc kiểm tra length sẽ không cần thiết vì chắc chắn nếu chuỗi a chứa chuỗi b thì theo lex order nó sẽ nằm sau chuỗi b. Mình suggest có thể thử replace đoạn substr bằng hàm hày sẽ tối ưu hơn, vì không cần tạo ra str tạm, cũng k bị error khi length ngắn hơn:

C++: 
words[i + 1].rfind(words[i], 0) == 0
 
Lập Trình Viên Gà said:
Với 1 dev trình bình thường, chưa luyện thuật toán bao giờ nên đi thẳng vào leetcode giải bài rồi học dần hay là kiếm sách học trước nhỉ các my fen?
Click to expand...
Mình thấy nên học trên HackerEarth trước, bên HackerEarth tổ chức bài bản hơn. Sau đó làm leetcode sẽ dễ hơn
https://www.hackerearth.com/practice/

Cày leetcode có thể theo study plan của leetcode hoặc theo bác Neetcode. Bác này tự cày và đậu Google, chia sẻ video chi tiết hướng dẫn giải miễn phí. https://neetcode.io/
 
tdat00 said:
Cũng mần daily leetcode mấy tháng nay rồi, ăn sáng uống cafe vào dành 1h để làm task cũng vui phết :smile:

View attachment 1220358
Click to expand...
Bác chăm làm thế. Em tranh thủ lúc nghỉ làm challenge mà vẫn miss mất mấy câu. Tháng này lại không có badge rồi.
1655701774384.png
 
_Gia_Cat_Luong_ said:
À đúng, vì fen dùng substr nên phải kiểm tra cái lenght chứ không sẽ bị lỗi, haha.
Ý mình là việc kiểm tra length sẽ không cần thiết vì chắc chắn nếu chuỗi a chứa chuỗi b thì theo lex order nó sẽ nằm sau chuỗi b. Mình suggest có thể thử replace đoạn substr bằng hàm hày sẽ tối ưu hơn, vì không cần tạo ra str tạm, cũng k bị error khi length ngắn hơn:

C++: 
words[i + 1].rfind(words[i], 0) == 0
Click to expand...
T hiểu rồi. :beauty:.
Thêm 1 cách nữa tối ưu hơn. K cần lật word trước, sửa lại cái hàm compare thôi.

C++: 
class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        sort(words.begin(), words.end(),
                [] (const auto &a, const auto &b) {
                    return lexicographical_compare(a.rbegin(), a.rend(), b.rbegin(), b.rend());
                    });
        
        int ret = 0;
        for (int i = 0; i < words.size()-1; ++i){
            if (!endsWith(words[i+1], words[i])) {
                ret += words[i].size() + 1;
            }
        }
        ret += words.back().size() + 1;
        
        return ret;
    }
    
    bool endsWith(const string &s, const string &sub){
        if (s.length() >= sub.length()) {
            return (0 == s.compare (s.length() - sub.length(), sub.length(), sub));
        } else {
            return false;
        }
    }
};
 
h.q.ng said:
Bác chăm làm thế. Em tranh thủ lúc nghỉ làm challenge mà vẫn miss mất mấy câu. Tháng này lại không có badge rồi.
View attachment 1220506
Click to expand...

Mình hay có thói quen vào công ty uống cafe đọc báo, giờ thì đổi sang làm task thôi. Làm nhiều nó quen dạng nên cũng nhanh ấy mà.

Sent from Samsung SM-A528B using vozFApp
 
tu_tay_bop_dai said:
Solution đơn giản nhất có thể nghĩ ra :)
C#: 
public class Solution {
    public int MinimumLengthEncoding(string[] words) {
        Array.Sort(words, (x, y) => x.Length.CompareTo(y.Length));
        var dup = new List<string>();
        int removed = 0, total = 0;
        for(int i=0; i < words.Length - 1; i++){
            total += (words[i].Length + 1);

            for(int j = i+1; j< words.Length; j++){
                if(words[j].EndsWith(words[i])){
                    removed += (words[i].Length + 1);
                    break;
                }
            }
        }
        return total - removed + words[words.Length -1].Length + 1;
    }
}

View attachment 1220370

Mới đầu quên break sau khi loại trừ substring nên fail lần đầu
Click to expand...
Solution này muốn optimize có thể xài Dictionary thay cho 2 vòng lập For.
 
Last edited:
tro` nay co ve vui nhi
Code: 
function minimumLengthEncoding(words) {
    return words.sort((a,b)=>-(a.length-b.length)).reduce((result,value,i )=>{
        let [s,indices]=result
        if(value.length>7){return result}
        
        let nValue = value+"#"
        let index = s.indexOf(nValue)
      
        if(index>=0){
            indices.push(index)
        }else{
            indices.push(s.length)
            s=s+nValue
        }
        return [s,indices]
    },["",[]])[0].length
};
 
Mấy bài leetcode medium kể ra với e cũng giải được cơ mà không tối ưu speed vs mem như bọn nó thôi , nhiều bài mình làm dài vl, bọn kia nó làm chục dòng, lại còn nhanh hơn mình :canny:

via theNEXTvoz for iPhone
 
LC hôm nay (20/06/2022):
#820. (Medium) https://leetcode.com/problems/short-encoding-of-words/

Phân tích bài toán:

1 <= n <= 2000: Có thể chạy từ O(n^2) trở xuống
  • Đây có vẻ là bài search string trong string
  • Từ ví dụ ta nhận thấy có vài điểm quan trọng:
    • Nếu 2 từ có phần đuôi (suffix) giống nhau thì chỉ có 1 từ xuất hiện trong chuỗi encoding
    • Và đó sẽ là từ dài hơn, tương tự nếu có n từ thì đó sẽ là từ dài nhất
    • Vì đề chỉ yêu cầu tính chiều dài chuỗi encoding, nên chắc không cần dựng lại nguyên cái chuỗi, chỉ cần tính tổng length của các từ trong chuỗi là đủ (và +1 vì thêm dấu # cuối mỗi từ)


Solution 1: Brute force O(n^2)
Bài toán trở thành tìm các chuỗi có chung suffix, ý tưởng về thuật toán brute-force có thể như sau:

Mã giả:

Code: 
result = 0
for each w1 in words {
   if <không có từ w2 trong words mà dài hơn w1 và w2.endswith(w2)> {
      result += w1.length + 1
  }
}

return result

Nhận xét:
  • Solution này chạy với độ phức tạp O(n^2), và khả thi với constraint bài toán.
  • Tuy nhiên có gặp edge case là trong mảng có các từ trùng nhau, các bạn có thể tự suy nghĩ cách fix.

Solution 2: Sort the list O(nlogn)
Solution 1 đã hoạt động nhưng ta nhận thấy bài toán có thể tối ưu thêm
  • Đầu tiên, ta nhận thấy thao tác tìm kiếm từ w2 rất kém hiệu quả, liệu có cách nào xác định ra từ w2 nhanh hơn không ?
  • Nếu bài toán là search prefix, ta có thể thử sort mảng words theo lex order
  • Đặc điểm của lex order là các string có chung prefix sẽ nằm liên tục với nhau nhau (như trong cuốn từ điển)
  • Nhưng bài này là search suffix => quá đơn giản, chỉ việc đảo ngược hết tất cả các chuỗi lại thì bài toán sẽ trở thành prefix
  • Vì sau khi sort, các từ có suffix giống nhau sẽ nằm liên tiếp nhau, nên từ w2 (nếu có) chắc chắn sẽ nằm ngay sau w1
  • Bài toán trở thành kiểm tra từ w1 với từ ngay phía sau nó

Mã giả như sau:

Code: 
for each w in words {
    <đảo ngược w>
}

words.sort() // mặc định các hàm sort string đều là theo lex order

result = 0
for i in 0..words.length {
    if (!words[i + 1].endswith(words[i])) { // out of bounds ?
        result += words[i].length + 1
    }
}
return result

Nhận xét:
  • Phần xử lý chính thật ra chỉ chạy với độ phức tạp là O(n), tuy nhiên hàm sort có đpt là O(nlogn) => đpt chung là O(nlogn)
  • Dĩ nhiên O(nlogn) là rất nhanh so với constraint 2000, và thật ra đây cũng là phương án tối ưu nhất (beats >95%)
  • Mã giả chỉ trình bày ý tưởng và sẽ không xử lý các trường hợp biên

Solution 3: Trie và Suffix HashSet O(n)
Nói chung mỗi khi gặp bài toán liên quan đến tìm kiếm string, hoặc prefix suffix hãy nghĩ ngay đến dùng Trie
  • Đây là một cấu trúc dữ liệu tối ưu cho các thao tác này và luôn có chi phí O(1) cho tất cả việc thêm / xóa / sửa / tìm kiếm (theo prefix)
  • Ngoài ra nếu lười implement Trie, ta có thể dùng Prefix HashSet cũng là một mô phỏng đơn giản của Trie, ý tưởng là ta sẽ insert toàn bộ các prefix của một string vào HashSet, khi đó việc tìm kiếm prefix đơn giản là check trong HashSet. Chi phí cũng tương tự như Trie đều là O(1) cho tất cả thao tác. Tuy nhiên cách này tốn bộ nhớ và mất thời gian build HashSet hơn.
  • Dĩ nhiên với bài toán suffix như thế này thì ta cần điều chỉnh chút ít, đảo ngược string với Trie, hoặc insert tất cả suffix thay vì prefix với HashSet

Mã giả:

Code: 
bags = <Trie hoặc HashSet>

for each w in words {
    <thêm w vào bags>
}

result = 0
for each w in words {
    if <nếu w không có trong bags> { // self check ?
        result += w.length + 1
    }
}
return result

Nhận xét:
  • Mặc dù solution này có độ phức tạp O(n), nhưng chí phí build bags là rất lớn nên trong khoảng vài ngàn phần tử thì solution 2 vẫn chạy nhanh hơn. Cách này chỉ thực sự out perform khi n lên đến trăm ngàn.
  • Cần xử lý thêm edge case là từ w sẽ luôn có trong bags (vì nó cũng là suffix của chính nó) và trong mảng có các từ trùng nhau
 
Last edited:

Similar threads

buiduchanh1995
thắc mắc Cách thiết kế database cho hệ thống lớn
2
Replies
37
Views
3K
khonganhit19
khonganhit19
meekoo
thắc mắc [Hỏi AI] Cách làm sao để train AI hiểu một task nào đấy?
Replies
9
Views
994
weed_bông
weed_bông
IM LANG
thắc mắc Cần cao nhân giúp đỡ về WordPress (có sử dụng custom theme bằng HTML, CSS)
Replies
3
Views
317
zaizai_vjp
zaizai_vjp
quangpt12345
kiến thức Join Anchor Consortium trading crypto sàn Odyssey kiếm lợi nhuận 2-3% mỗi ngày
Replies
4
Views
160
quangpt12345
quangpt12345
J
kiến thức Mod Mộng Liêu Trai mới nhất
Replies
0
Views
95
jivrus
J

Share this page

Back
Top