의문 :

문자열 제품의 배열과 searchWord 문자열이 주어집니다. 우리는 searchWord의 각 문자가 입력되면 상품에서 최대 3개의 상품명을 제안하는 시스템을 설계하고자 합니다. 제안된 제품은 searchWord와 공통 접두사를 가져야 합니다. 공통 접두사가 있는 제품이 3개 이상 있는 경우 3개의 사전식 최소 제품을 반환합니다.

searchWord의 각 문자가 입력된 후 제안된 제품 목록 목록을 반환합니다.

샘플 테스트 사례:

예 1:

입력: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
출력: [
["모바일","머니팟","모니터"],
["모바일","머니팟","모니터"],
["마우스","마우스패드"],
["마우스","마우스패드"],
["마우스","마우스패드"]
]
설명: 사전순으로 정렬된 제품 = ["모바일","머니팟","모니터","마우스","마우스패드"]
m 및 mo를 입력한 후 모든 제품이 일치하고 사용자 ["mobile","moneypot","monitor"]가 표시됩니다.
mou, mous 및 mouse를 입력하면 시스템에서 ["mouse","mousepad"]를 제안합니다.

예 2:

입력: products = ["havana"], searchWord = "havana"
출력: [["하바나"],["하바나"],["하바나"],["하바나"],["하바나"],["하바나"]]

예 3:

입력: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
출력: [["수하물","가방","배너"],["수하물","가방","배너"],["수하물","가방"],["가방"]]

예 4:

입력: products = ["havana"], searchWord = "tatiana"
출력: [[],[],[],[],[],[],[]]

제약

1 <= 제품.길이 <= 1000

제품에 반복되는 요소가 없습니다.

1 <= Σ 제품[i].길이 <= 2 * 10^4

products[i]의 모든 문자는 영문 소문자입니다.

1 <= searchWord.length <= 1000

searchWord의 모든 문자는 영문 소문자입니다.

접근하다 :

이 질문은 Trie 데이터 구조를 사용하여 접근할 수 있습니다. 여기서 접두사를 관리해야 하며 Trie 데이터 구조를 사용할 때 접두사를 찾는 것이 매우 간단합니다.
우리의 trie 데이터 구조에는 크기가 26인 TrieNode 배열과 질문에 따라 상위 3개 제안을 저장하기 위한 연결된 문자열 목록이 있습니다.

따라서 Trie 구조는 다음과 같습니다.

class TrieNode {
    TrieNode [] child = new TrieNode [26];
    LinkedList<String> suggestion = new LinkedList<>();
}

끼워 넣다

삽입, 검색 등과 같은 몇 가지 기본 작업을 수행하고 이 게시물을 따라 삽입 방법에 대한 기본 아이디어를 얻으십시오.

Trie 데이터 구조 - 삽입 연산

Rohith V ・ 5월 9일 ・ 4분 읽기

#java #algorithms #tutorial #interview

여기서 제안 연결 리스트에 단어를 추가하고 추천 단어가 3개뿐이므로 연결 목록의 크기가 3을 초과하면 마지막 단어를 삭제하는 트릭을 만듭니다.

public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()){
            int index = ch - 'a';
            if (node.child[index] == null) {
                node.child[index] = new TrieNode();
            }
            node = node.child[index];
            node.suggestion.offer(word);
            if (node.suggestion.size() > 3) {
                node.suggestion.pollLast();
            }
        }
    }

여기에서 특정 문자를 누를 때마다 존재하지 않는 경우 새 노드가 생성되고 해당 단어가 연결 목록에 제안으로 추가됩니다.

따라서 단어를 삽입한 후
다음과 같은 구조:

검색

이제 매우 간단합니다. searchWord 내부의 각 문자를 살펴보고 해당 문자의 각 노드를 찾고 결과에 제안을 추가합니다. 캐릭터가 트라이에 노드가 없으면 결과에 빈 값을 추가합니다.

  public List<List<String>> search(String searchWord) {
        List<List<String>> result = new ArrayList<>();
        TrieNode node = root;
        for (char ch : searchWord.toCharArray()) {
            int index = ch - 'a';
            if (node != null) {
                node = node.child[index];
            }
            result.add(node == null ? Arrays.asList() : node.suggestion);
        }
        return result;
    }

전체 코드:

class Solution {

    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()){
            int index = ch - 'a';
            if (node.child[index] == null) {
                node.child[index] = new TrieNode();
            }
            node = node.child[index];
            node.suggestion.offer(word);
            if (node.suggestion.size() > 3) {
                node.suggestion.pollLast();
            }
        }
    }

    public List<List<String>> search(String searchWord) {
        List<List<String>> result = new ArrayList<>();
        TrieNode node = root;
        for (char ch : searchWord.toCharArray()) {
            int index = ch - 'a';
            if (node != null) {
                node = node.child[index];
            }
            result.add(node == null ? Arrays.asList() : node.suggestion);
        }
        return result;
    }


    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        for (String product : products) {
            insert(product);
        }
        return search(searchWord);
    }
}

class TrieNode {
    TrieNode [] child = new TrieNode [26];
    LinkedList<String> suggestion = new LinkedList<>();
}

복잡성:

복잡성은 Trie를 구축하는 과정과 searchWord의 길이에 따라 다릅니다. Trie를 구축하는 데 소요되는 시간은 O(m * m * n)입니다. 문자열 비교를 포함하기 때문에 각 비교에 O(m)이 소요됩니다. 그러므로,
시간: O(m * m * n + L), 공백: O(m * n + L * m) - 반환 목록 ans 포함, 여기서 m = 제품의 평균 길이, n = products.length, L = searchWord.length ().

Rohithv07 / LeetCode

해결된 LeetCode 문제.

LeetCode

해결된 LeetCode 문제.


View on GitHub