Ví dụ:
"abcdefgh" trả về true
"abadefghi" trả về false vì a xuất hiện 2 lần.
Cách làm đơn giản:
- Duyệt từng phần tử
- Tìm trong danh sách phần tử còn lại có phần tử nào giống không.
Time complexity sẽ là O(n * timecomplexity của tìm).
Tuỳ vào cách cài đặt phần tìm chúng ta có thể có O(n * n), O(n * logn), O(n * 1).
BCR: O(n)
BruteForce: O(n^2)
Để đạt được O(1) việc tìm kiếm, chỉ cần đưa các ký tự vào HashTable là có thể tìm được với O(1) time.
func isUnique(_ str: String) -> Bool {
var dict: [Character: Bool] = [:]
for char in str {
if dict[char] == true {
return false
}
dict[char] = true
}
return true
}
Tuy nhiên do yêu cầu đề bài chúng ta không được dùng thêm DataStructure nào nên việc dùng HashTable ở đây tốn Space.
Chúng ta có thể tự cài đặt HashTable riêng để thoả mãn yêu cầu.
Hoặc có cách tiếp cận khác dựa vào kiến thức sau đây:
Bitwise XOR:
0 ^ n = n
n ^ n = 0
ví dụ : 0 ^ 1 = 1, 1 ^ 1 ^ 2 = 0 ^ 2 = 2
Chúng ta tự hiện chuyển đổi từng ký tự trong string thành Int (bằng hàm hashValue có sẵn hoặc tự viết), xor với kết quả trước đó sau đó kiểm tra.
func isUnique2(_ str: String) -> Bool {
var toTest: Int = 0
var previousToTest: Int = 0
for char in str {
let hash = char.hashValue //Hàm có sẵn của swift
let sample = toTest ^ hash
//Nếu giá trị mới làm quay về kết quả xor trước đó thì dừng
if sample == previousToTest {
return false
}
previousToTest = toTest
toTest = sample
}
return true
}
Happy Cheating!