Liệt kê từ trong câu và sắp xếp theo số lần xuất hiện giảm dần với số lần xuất hiện

chử HOC vs hoc có khác nhau không a :D, phải khác nhau chứ

Dùng Python libraries, mẫu thử 1000 lần

import re, time
from collections import Counter

SAMPLE = 1000

str = "day nhau hoc. hoc nhau day. HOC hoc ?? ^_^ day day. day MA khong hoc."

start = "%.50f" % time.time()
print(Counter(re.compile('[^a-zA-Z\s]').sub('', str).split()))
for i in range(0,SAMPLE-1): 
    Counter(re.compile('[^a-zA-Z\s]').sub('', str).split())
stop = "%.50f" % time.time()

print((float(stop) - float(start))/SAMPLE),
print("(s)")

Output:

Counter({'day': 5, 'hoc': 4, 'nhau': 2, 'MA': 1, 'HOC': 1, 'khong': 1})
9.0000629425e-06 (s)

Time complexity: ~10 us
Space complexity: đang tìm hiểu

Dùng radix sort

def split_word(s):

    s=s.lower()
    i=0
    ans=[]

    while i<len(s):
        if s[i].isalpha():
            word=""
            while s[i].isalpha() and i<len(s):
                word+=s[i]
                i+=1
            ans.append(word)
        i+=1
    return ans

def radix_sort(lst,i):
    if len(lst)<=1:
        return lst
    sorted_list=[]
    bucket=[[] for x in range(26)]

    for word in lst:
        if i>=len(word):
            sorted_list.append(word)
        else:
            
            bucket[ord(word[i])-ord('a')].append(word)
    sorted_bucked=[radix_sort(b,i+1) for b in bucket]
    return sorted_list+[word for  lst in sorted_bucked for word in lst]

def counter(lst):

    ans=[]

    for v in lst:
        if len(ans)==0 or v!=ans[-1][0]:
            ans.append([v,1])
        else:
            ans[-1][1]+=1
    return ans

for k,v in sorted(counter( radix_sort(split_word("day nhau hoc. hoc nhau day. \
HOC hoc ?? ^_^ day day. day MA khong hoc."),0)),reverse=True,key=lambda x:x[1]):
    print k,":",v

Time, space : O(n*|w|)

Tận dụng mọi thứ có thể của java

package test;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Test {

	public static void main(String[] args) {
		
		Map<String, Integer> mapString = new HashMap<String, Integer>();
		String sourceStr = "day nhau hoc. hoc nhau day. HOC hoc ?? ^_^ day day. day MA khong hoc".toLowerCase();
		String[] des = sourceStr.split("[^a-zA-Z0-9']+");
		System.out.println(Arrays.asList(des));
		mapString.put(des[0], 1);
		for (int i = 1; i < des.length; i++) {
			if (mapString.containsKey(des[i])) {
				int currentVal = mapString.get(des[i]);
				mapString.put(des[i], ++currentVal);
			} else {
				mapString.put(des[i], 1);
			}

		}
		Map<String, Integer> sortedMap = sortByValue(mapString);
		for (Map.Entry m : sortedMap.entrySet()) {
			System.out.println(m.getKey() + " " + m.getValue());
		}

	}

	private static Map<String, Integer> sortByValue(Map<String, Integer> unsortMap) {

		// 1. Convert Map to List of Map
		List<Map.Entry<String, Integer>> list = new LinkedList<Map.Entry<String, Integer>>(unsortMap.entrySet());

		// 2. Sort list with Collections.sort(), provide a custom Comparator
		// Try switch the o1 o2 position for a different order
		Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
			public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
				return (o2.getValue()).compareTo(o1.getValue());
			}
		});

		// 3. Loop the sorted list and put it into a new insertion order Map
		// LinkedHashMap
		Map<String, Integer> sortedMap = new LinkedHashMap<String, Integer>();
		for (Map.Entry<String, Integer> entry : list) {
			sortedMap.put(entry.getKey(), entry.getValue());
		}

		return sortedMap;
	}

}

Mọi người giải thích thuật toán của mình ra luôn được không? Vì bài này mình cho phép dùng mọi ngôn ngữ, nên tốt nhất là nói luôn giải thuật để người khác đọc vào hiểu được.

P/S: Đạt không nghĩ là bài này lại có nhiều giải pháp overkill như vậy.

P/S2: Đạt giải bài này dùng cách tương tự như @nguyenhuuca, dùng unordered_map

Bước 1: Tách từng từ trong chuỗi ra
Bước 2: Dùng mỗi từ là key trong unordered_map, value là count của từ đó. Với cách này mình sẽ có O(n)
Bước 3: Chuyển cái kết quả từ map sang vector, sort lại. Với bước này mình sẽ tốn O(mlogm) với m là số lượng từ đã sắp xếp trong câu. m <= n.

Tổng phức tạp của bài này là O(n + mlogm), giả sử m << n thì coi như O(n)
Space complexity: O(m), với m là số lượng từ trong trong kết quả

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<pair<string, int>> solution(string inputStr) {
    string word;
    unordered_map<string, int> map;
    for(char c : inputStr) {
        if(isspace(c)) {
            if (!word.empty()) {
                map[word]++;
                word.clear();
            }
        } else if (isalnum(c)){
            word.push_back(tolower(c));
        }
    }
    map[word]++;

    vector<pair<string, int>> ans;
    for(auto p : map) {
        ans.push_back(make_pair(p.first, p.second));
    }

    sort(ans.begin(), ans.end(), [](const std::pair<string,int>  &left, const std::pair<string,int>  &right){
         return left.second > right.second;
         });
    return ans;
}

int main() {
    vector<pair<string, int>> ans = solution("day nhau hoc. hoc nhau day. ?? ^_^ HOC hoc day day. day MA khong hoc.");
    for(auto e : ans) {
        cout << e.first << " : " << e.second << endl;
    }
}

Cái em dùng giống anh Đạt rồi, khỏi giải thích nhỉ :))

tính cmt mà ai cũng đưa sol hết rồi :’(

Kiếm bài khác đưa lên giải chơi Phúc.