Thuật toán tìm ra unique string

Giới thiệu

Chả là câu chuyện thế này ạ: Lâu lâu rồi mình có đọc quyển sách crack coding interview để xem những câu hỏi code tuyển dụng của mấy hàng khủng như google, facebook sẽ như thế nào? Ngay khi đọc câu hỏi đầu tiên mình đã phải thốt lên: chả nhẽ đây lại là câu hỏi tuyển dụng của một công ty lớn? Nội dung câu hỏi là: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?"

Nội Dung

Theo lẽ thông thường thì lưu đồ của bài toán sẽ là như thế này ạ:

Và đây là cách chúng ta code:

function (string) {
  var char_set = {};
  for (var i = string.length - 1; i >= 0; i--) {
    if (char_set[string[i]]) {
      return false;
    }
    char_set[string[i]] = true;
  }
  return true
}

Nhưng liệu một giải thuật như vậy đã gọi là đầy đủ? Tất nhiên không. Về cơ bản thì không có cách nào khác có thể nằm ngoài lưu đồ của bài toán, nghĩa là bắt buộc phải follow theo đúng từng đó bước trong lưu đồ cho dù bạn có thể dùng giải thuật j. Trước tiên mình sẽ nói về những nhược điểm của giải thuật kia. Nhược điểm:

• Đầu tiên đó là về số kí tự: bạn cần phải biết đây là một chuỗi string unicode hay là một chuỗi string ASCII vì đối với ASCII số kí tự của nó là hữu hạn (256 kí tự). Và trong trường hợp đoạn string là ASCII thì chúng ta nên bổ xung thêm điều kiện đếm length.

if (string.length > 256 ) {
  return false
}

• Thứ 2 là với một string unicode với một số lượng kí tự khủng như với bảng mã đó thì việc tạo ra một mảng để lưu các kí tự đã bị lặp qua sẽ rất to, và đây là một điểm chúng ta cần phải xử lí để cho thuật toán khi chạy không bị tốn tài nguyên. Vì suy cho cùng mảng đó được tạo ra chỉ để lưu trữ trạng thái của những phần tử đã được lặp rồi. và cách mà chúng ta sẽ sử dụng đó là dùng BITWISE. Và đây là giải thuật của nó:

function (string) {
	int checker = 0;
	for (var i = string.length - 1; i >= 0; i--) {
		var string.charAt(i) - "a";
		if ((checker & (1 << val)) > 0) {
			return false
		}
		checker |= (1 << val);
	}
	return true
}

Giải thích :

• Phép toán 1 << val có nghĩa là dịch trái 1 đi val đơn vị, khi đó 1 << val sẽ tương đương 10....0 với val số 0 ở đằng sau.
• Khi đó với giá trị checker = 0 => biểu thức (checker & (1 << val)) > 0 luôn = 0. Mệnh đề này chỉ true (báo hiệu chuỗi string này không unique) khi và chỉ khi giá trị bit tại cùng một vị trí của checker và 1<< val đều là 1. Vậy khi nào thì giá trị của checker và (1 << val ) đều là 1? Hiểu nôm na (1 << val ) có thể coi là giá trị index của kí tự, tại vị trí thứ val thì giá trị của (1 << val ) là 1. Còn checker ngay sau khi kiểm tra và xác nhận chưa tồn tại kí tự trong chuỗi, ta sẽ thực hiện phép hoặc với (1 << val) và gán nó vào checker lúc này những kí tự đã được loop qua sẽ sẽ có ra giá trị index tương ứng trong checker là 1. Và khi bị loop qua lần nữa chuỗi sẽ bị đánh dầu là non unique. Note: var string.charAt(i) - "a"; dòng này có nghĩa là chỉ tính các kí tự từ a đến z vì số bit của kiểu interger là hữu hạn (Theo đúng ý tác giả). Nếu tính cả các kí tự khác thì có lẽ vẫn phải dùng mảng để lưu trạng thái đã check.

Kết luận

Trên đây là phàn mình trình bày lại bài toán theo ý hiểu của mình. Rất mong nhận được sự góp ý ạ.