Podział słów

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

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

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