BastterCode semana 19 - 28. Implement strStr() - Tecnologia

Chat Ao Vivo

Moderador:
Assunto:

BastterCode semana 19 - 28. Implement strStr()
comentada em 24/08/2023 18:25

Tecnologia

comentada em 24/08/2023 18:25

Mais um desafio semanal.

Não me apareçam aqui usando substring pré-pronto, que eu to cheio de voadora atômica na carteira!!!

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:
1 <= haystack.length, needle.length <= 104
haystack and needle consist of only lowercase English characters.

Link: Explore - LeetCode

Comentários

Último comentário Só moderadores Só quem eu sigo Ordenar por gostei

oxe

em 04/07/2023 21:23

class Solution {
public:
    int strStr(string haystack, string needle) {
        const short nsize = needle.size(), hsize = haystack.size();
        
        if (nsize > hsize) return -1;
        
        for (short i = 0; i <= hsize - nsize; ++i) {
            for (short j = 0; j < nsize; ++j) {
                if (haystack[i + j] != needle[j]) break;
                else if (j == nsize - 1) return i;    
            }
        }   
        
        return -1;
    }
};

; 0;

'; 0';

Ajuda aí pow!

BastterCode semana 19 - 28. Implement strStr() - #1 de 5

Lut
em 05/07/2023 18:55

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if (needle not in haystack):
            return -1
        else:
            checa_cond = False
            len_palavra = len(haystack)
            len_teste = len(needle)
            for i in range(len_palavra):
                if needle[0] == haystack[i]:
                    aux = i
                    for j in range(len_teste):
                        if needle[j] == haystack[aux]:
                            checa_cond = True
                            aux = aux + 1
                        else:
                            checa_cond = False
                            break
                    if checa_cond == True:
                        return i

Solução chata (Python)

.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

Solução simples (Python)

; 0;

'; 0';

Ajuda aí pow!

BastterCode semana 19 - 28. Implement strStr() - #2 de 5

oxe

em 11/07/2023 17:54

Tava lendo sobre branchless code. É um conceito que exige conhecimento de assembly pra implementar e de qualquer forma, segundo o texto que li, aparentemente é menos útil hoje em dia, pois os melhores compiladores identificam vários padrões e eliminam muitos branches do código.

Mesmo assim resolvi brincar com o pouco que consegui entender da ideia geral. Afinal, programação é um hobby mesmo kkk.

class Solution {
public:   
    auto strStr(const string& haystack, const string& needle)->short {
        constexpr char not_found = -1;
        const short nsize = needle.size(), hsize = haystack.size();               
        
        short i = 0, p = -1;
        
        while (i > p && i <= hsize - nsize) {
            short j = 0;
            p = i;
            
            while (j < nsize && haystack[i + j] == needle[j]) ++j;
            i += (j < nsize);
        }
        
        return (i > p)*(not_found) + (!(i > p))*(i);
    }
};?

; 0;

'; 0';

Ajuda aí pow!

BastterCode semana 19 - 28. Implement strStr() - #3 de 5

shadow_walker

em 23/08/2023 20:06

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        ans = -1
        if needle in haystack:
            ans = haystack.index(needle)
        return ans

; 0;

'; 0';

Ajuda aí pow!

BastterCode semana 19 - 28. Implement strStr() - #4 de 5

oxe

em 24/08/2023 18:25

Estudando um pouco sobre as ferramentas do STL.

class Solution 
{
public:   
    auto strStr(const string& haystack, const string& needle) 
    {
        auto it = std::search
                  (haystack.begin(), 
                   haystack.end(),
                   std::boyer_moore_searcher
                  (needle.begin(), 
                   needle.end()));             
                                                                                   
        return it == haystack.end() ? 
                -1 : 
                std::distance(haystack.begin(), it);
    }
};?