Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/
1. Mở đầu
Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.
2. Đề bài
Cho bạn một mảng các chuỗi tên words và một chuỗi tên chars.
Một chuỗi được cho là hợp lệ nếu nó được tạo bởi các chữ cái từ chars, tuy nhiên mỗi chữ cái chỉ được sử dụng một lần.
Trả về kết quả là tổng độ dài của tất cả các chuỗi hợp lệ trong words.
Điều kiện:
1 <= words.length <= 1000.1 <= words[i].length, chars.length <= 100.words[i]vàcharschứa các chữ cái tiếng Anh viết thường.
Ví dụ 1:
Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.
Ví dụ 2:
Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.
3. Phân tích
Âu kê, đề bài này cũng đơn giản không quá phức tạp. Về cơ bản đề bài yêu cầu chúng ta trả về kết quả là độ dài của tất cả các chuỗi hợp lệ có trong mảng words. Ok, vậy muốn có các chuỗi hợp lệ này, ta phải kiểm tra chúng đã.
Để kiểm tra xem chuỗi trong mảng words có hợp lệ hay không, chúng ta phải dựa vào chuỗi chars. Chuỗi hợp lệ sẽ là chuỗi sử dụng các chữ cái từ chuỗi chars tạo thành, mỗi chữ cái chỉ được dùng một lần. Nghĩa là sao?
Như trong ví dụ 1:, ta có chuỗi "cat" cần kiểm tra, ta thấy chuỗi chars = "atach", vậy để tạo ra được chuỗi "cat", thì chuỗi chars sẽ dùng ba chữ cái là 'c', 'a', 't’ và số lượng chữ cái còn lại của chars sẽ là [a,h].
Tương tự như vậy với chuỗi "hello" và chars = "helo". Để tạo ra được chuỗi "hello" thì chuỗi chars sẽ dùng 'h', 'e', 'l', 'o',. Tuy nhiên chuỗi chars lại chỉ có một chữ cái 'l’, nên chuỗi "hello" này không phải là chuỗi hợp lệ.
Và để kiểm tra xem chuỗi có hợp lệ hay không, chúng ta sẽ sử dụng kiểu dữ liệu HashMap để giải quyết. Với key sẽ là chữ cái có trong chars và value sẽ tương ứng với số lần xuất hiện của chữ cái đó. Sau đó ta sẽ duyệt qua từng chữ cái của mỗi chuỗi có trong words, nếu chữ cái nào có xuất hiện trong map và số lần xuất hiện của nó lớn hơn 0, ta sẽ trừ số lần xuất hiện đi 1, nếu đến hết chuỗi mà số lần xuất hiện của mỗi chữ cái đều lớn hơn hoặc bằng 0 thì ta trả về true; còn nếu chữ cái nào tuy có xuất hiện trong map nhưng số lần xuất hiện của nó nhỏ hơn hoặc bằng 0 (như ví dụ helo ở trên) thì ta trả về false.
Sau khi kiểm tra xong, nếu có chuỗi nào hợp lệ thì ta cộng dồn độ dài của chuỗi ấy lại, rồi trả về kết quả tổng là xong.
Done! Sang bước tiếp theo thôi.
4. Code bằng cơm
Đầu tiên chúng ta sẽ tạo ra một HashMap với key là chữ cái có trong chars, còn value là số lần xuất hiện của chúng.
Để làm công việc kiểm tra như phân tích ở trên, chúng ta sẽ có riêng một function chuyên làm việc này, với đầu vào là một chuỗi word, cùng với đó là map chúng ta vừa tạo ra ở trên.
Bây giờ chúng ta sẽ làm một vòng lặp xét từng chữ cái của word, nếu chữ cái nào có tồn tại trong map đồng thời số lần xuất hiện của nó phải lớn hơn 0, ta trừ số lần xuất hiện đi 1.
Hãy thử với chuỗi "cat" nhé, đầu tiên ta có chữ cái c, nó thỏa mãn điều kiện chúng ta vừa nêu, nên ta sẽ trừ số lần xuất hiện của nó ở trong map đi 1:
Tiếp theo đến chữ a, ta thấy thỏa mãn điều kiện trên nên trừ đi số lần xuất hiện:
Cuối cùng là chữ t, ta thấy nó cũng thỏa mãn điệu kiện trên:
Vậy suy ra chuỗi "cat" này là chuỗi hợp lệ. Sau đó ta chỉ việc lấy độ dài của chuỗi hợp lệ "cat" là 3 cộng dồn cho các chuỗi hợp lệ khác có trong mảng words là sẽ ra kết quả cuối cùng thôi.
5. Code chạy bằng máy
Code của chúng ta sẽ như sau:
public static int countCharacters(String[] words, String chars) {
int res = 0;
HashMap<Character, Integer> map = new HashMap<>();
char[] arrCh = chars.toCharArray();
for (char c : arrCh) {
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
for (String string : words) {
if(check(string, map)){
res += string.length();
}
}
return res;
}
public static boolean check(String word, HashMap<Character, Integer> map){
char[] arrW = word.toCharArray();
for (char c : arrW) {
if (map.containsKey(c) && map.get(c) > 0) {
map.put(c, map.get(c) - 1);
} else {
return false;
}
}
return true;
}
6. Kết thúc
Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!
Bình luận