Làm thế nào để tìm từ đầu tiên trong chuỗi không bị lập lại? | How to find the first non repeated character in A string?

Trong các kỳ thi tuyển dụng bằng văn bản hoặc phỏng vấn kỹ tuật của Amazon, bạn có thể dễ dàng tìm thấy công hỏi này. Vì thế để giúp bạn chuẩn bị tốt cho cuộc phỏng vấn chúng tôi đăng câu trả lời cho câu hỏi này trong bài viết này. Điều đầu tiên chúng ta cần tìm hiểu rõ câu hỏi và yêu cầu của nó, chúng ta cần viết một thuật toán để xác định ký tự đầu tiên không bị lập lại trong một chuỗi (String) ví dụ như:

• Với từ "stress" thì ta có chữ "t" là ký tự đầu tiên không bị lập lại trong chuỗi (string).
• Với từ "teeter" thì ta có chữ "r" là ký tự đầu tiên không bị lập lại trong chuỗi (string).

Logic Analyze  - Phân Tích Luận Lý Học

Như chúng ta đã biết một ký tự không lập lại thì sẽ chỉ xuất hiện chỉ một lần duy nhất trong chuỗi (String). Như vậy nếu chúng ta lưu trữ số lần xuất hiện của mỗi ký tự xuất hiện trong chuỗi (string), thì nó sẽ giúp chúng ta nhận diện được các ký từ nào sẽ không bị lập lại trong chuỗi. Vì thế chúng ta cần phải quét qua toàn bộ các ký tự trong chuỗi và xác định số lượng của chúng. Khi việc quét số lượng của mỗi ký tự trong chuỗi kết thúc, thì ký tự đầu tiên của chuỗi có số lượng là 1 thì nó là ký tự đầu tiên không bị lập lại của một chuỗi.


Pseudo Algorithm - Giả Thuật Toán

Đầu tiên tạo một biến đếm character cout hash table.

    For each character
        If there is no value stored in the character
            set it to 1 .
        else
            increment the value of the character by 1 .

Thứ hai quét chuỗi(string).

    For each character
        return character if the count in hash table is 1 .
        If no character have count 1 , return null

Code Write - Viết Code

import java.util.HashMap;
import java.util.Scanner;

public class FirstNonRepeated {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(" Please enter the input string :");
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char c = firstNonRepeatedCharacter(s);
        System.out.println("The first non repeated character is :  " + c);
       
    }

    public static Character firstNonRepeatedCharacter(String str) {
        HashMap<Character, Integer> characterhashtable = new HashMap<Character, Integer>();
        int i, length;
        Character c;
        length = str.length();  // Scan string and build hash table
        for (i = 0; i < length; i++) {
            c = str.charAt(i);
            if (characterhashtable.containsKey(c)) {
                // increment count corresponding to c
                characterhashtable.put(c, characterhashtable.get(c) + 1);
            } else {
                characterhashtable.put(c, 1);
            }
        }
        // Search characterhashtable in in order of string str

        for (i = 0; i < length; i++) {
            c = str.charAt(i);
            if (characterhashtable.get(c) == 1) {
                return c;
            }
        }
        return null;
       
    }
   
}