Podział słów

Poziom trudności Średni
Często zadawane pytania Adobe Amazonka Apple Bloomberg ByteDance eBay Facebook Google Microsoft wyrocznia Qualtrics Uber VMware Yahoo
Algorytmy kodowanie Programowanie dynamiczne Wywiad przygotowanie do rozmowy kwalifikacyjnej LeetKod LeetCodeRozwiązaniaodwiedzajacy 70

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Podział słów to problem, który pięknie ilustruje zupełnie nową koncepcję. Wszyscy słyszeliśmy o słowach złożonych. Słowa złożone z więcej niż dwóch słów. Dzisiaj mamy listę słów i wszystko, co musimy zrobić, to sprawdzić, czy wszystkie słowa ze słownika pasują do naszego słowa złożonego. Nie marnując więcej czasu, przejdę do przypadku testowego, aby trochę wyjaśnić.

Przykład

Dane wejściowe: String = LeetCode; Słownik: [„Leet”, „Code”]

Wyjście: prawda

Przyjrzyjmy się przypadkowi testowemu, w którym również powinniśmy uzyskać fałsz

Dane wejściowe: String = Applepinkraft; Słownik: [„Apple”, „Pink”, „Kraft”]

Wynik: fałsz

Wyjaśnienie

Przyjrzyjmy się pierwszemu przypadkowi testowemu, aby rozwiązać ten problem z podziałem słów.

  • Tworzymy boolean szyk dla wszystkich postaci. Niech to będzie sprawdzone.
  • Ustawimy domyślne wartości na false
  • check [i] = true, jeśli podciąg (0, i) można złożyć ze słów ze słownika
  • check [0] = true, ponieważ podciąg (0,0) spełnia warunek
  • Dla każdego i
    • Zapętlamy wszystkie możliwe podciągi.
    • Co sprawia, że ​​podciąg się kwalifikuje?
      • Powinien zaczynać się od końca ostatniego segmentu, tj. Sprawdź [j] = true
      • substring (j, i) będzie częścią słownika
    • Zaznacz check [i] true dla wszystkich kwalifikujących się podciągów
  • Jeśli check [string.length ()] jest prawdą, możemy być pewni, że plik ciąg kwalifikowalne

Początkowa tablica logiczna może być przedstawiona jako

Podział słów zilustrowany na przykładzie LeetCode
Podział słów zilustrowany na przykładzie LeetCode

Tablica pozostaje taka sama, gdy wartości I to 2 i 3.

Ponieważ i = 4 zaczynamy skanowanie od 0 i voila !. Znaleźliśmy nasze pierwsze słowo.

Zaznaczamy check [4] jako prawdę i kontynuujemy nasze wyszukiwanie

Sprawdzanie dzielenia wyrazów w dalszej części
Sprawdzanie dzielenia wyrazów w dalszej części

Podczas sprawdzania brane są pod uwagę słowa zaczynające się od 0 i 4

Tak jak znajdujemy CODE. Przekształcamy check [8] na prawdę i w ten sposób zwracamy prawdę jako naszą odpowiedź.

Oto prosty kod, który można połączyć z powyższym wyjaśnieniem

Realizacja

Kod Java do podziału słów

class Solution 
{
    public boolean wordBreak(String s, List<String> wordDict) 
    {
        boolean check[]=new boolean[s.length()+1];
        check[0]=true;
        for(int i=1;i<=s.length();i++)
        {
            for(int j=0;j<i;j++)
            {
                //check[j] helps us to figure out new words without overlaps
                if(check[j] && wordDict.contains(s.substring(j,i)))
                {check[i]=true;break;}
            }
        }
        return check[s.length()];
    }
}

Kod C ++ do dzielenia wyrazów

class Solution 
{
public:
    bool wordBreak(string s, vector<string>& vec) 
    {
        vector<bool> check(s.size()+1,false);
        check[0]=true;
        int start=0;
        std::vector<string>::iterator it; 
        for(int i=1;i<=s.length();i++)
        {
            for(int j=start;j<i;j++)
            {
                if(check[j]==true)
                {
                    string word=s.substr(j,i);
                    it = std::find (vec.begin(), vec.end(), word); 
                    if (it != vec.end()) 
                    {check[i]=true;break;}
                }
            }
        }
        return check[s.length()];   
    }
};
String: LeetCode  
Dictionary: ["Leet","Code"]
true

Analiza złożoności

Złożoność czasowa: O (n ^ 2), gdzie n jest długością tablicy. Tutaj używamy zagnieżdżonej pętli for, w której druga pętla jest uruchamiana i razy, a pierwsza - n razy.

Złożoność przestrzeni: O (n), ponieważ tworzymy wektor o rozmiarze n do przechowywania informacji w kategoriach prawdy lub fałszu.

Istnieje wiele problemy ze strunami mamy, które możesz sprawdzić, aby uzyskać więcej ćwiczeń.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »