BastterCode semana 7 - Longest Common Prefix
comentada em 01/03/2023 20:16

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        
        // finds the length of the shortest word in strs
        var shortestLen: Int = 200 // 200 is maximum, given by problem
        strs.forEach{
            if (it.length < shortestLen) shortestLen = it.length
        }

        var output: String = "" // output string, starts empty

        // 1st loop, for every char
        for (charPosition in 0 until shortestLen){
            var auxChar: Char = strs[0][charPosition] // char for comparison, taken from 1st word
         
        // 2nd loop, for every word in strs
            for (word in strs){
                if (word[charPosition] != auxChar) return output
            }
            output += auxChar // if true adds char to the output
        }
        return output
    }
}

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) //input é um vetor de palavras
{
        int count = 0, size = strs.size(), word_index = count/size;

//se interpretarmos o vetor de palavras como uma matriz, as palavras seriam as linhas da
//matriz. Como os índices começam no 0, então strs[0][0] seria a 1° letra da 1° palavra, 
//strs[0][2] seria a 3° letra da 1° palavra e strs[2][0] seria a 1° letra da 3° palavra. 

//O algoritmo vai percorrer as letras das palavras pela ordem das letras, ou seja, olha
//a primeira letra em todas as palavras, depois a segunda letra, etc. Ele faz isso até
//achar uma inconsistência. 

//A inconsistência pode ser: 1- letras distintas na mesma posição; ou 2- ausência de 
//letra na palavra seguinte (ou seja, ela é mais curta). Nos dois casos, já chegamos ao 
//tamanho máximo das letras em comum entre palavras. A primeira inconsistência é testada
//diretamente no statement do while e a segunda é testada por um if dentro de cada laço. 

//Para percorrer as letras pela sua ordem, mudando as palavras, basta que o 1° índice da
//matriz varie de forma que ele retorne a 0 quando chegar à última palavra e só aí o 2°
//índice aumente. As operações aritméticas de modulo (%) e divisão (/) permitem isso se
//feitas entre um contador sempre crescente e o número de palavras na matriz. 

//Enquanto o contador for inferior a um múltiplo do n° de palavras, o modulo aumenta, e, 
//quando chega ao múltiplo, o módulo retorna a 0. Já a divisão é truncada, ou seja, 
//descarta o resto. Isso significa que a divisão só aumenta quando o contador chega a um 
//múltiplo do n° de palavras. 

//Pelo mesmo motivo, a divisão vai indicar a última posição em comum a todas as palavras.
//A resposta será a string formada por qualquer uma das palavras desde a posição inicial
//até essa posição, exceto se a posição for zero, pois aí não haverá letra em comum e o
//retorno será da string vazia "".

//o contador precisa aumentar antes da divisão para permitir testar o tamanho da próxima
//palavra antes de iniciar outro laço do while (evitando erro por referenciar um elemento
//que não existe na palavra seguinte).
   
        while (strs[count % size][word_index] == strs[0][word_index])
        {      
            count++;        
            word_index = count/size;
            
            if (word_index >= strs[count % size].size())
            {
                break;
            }
        }
        
        if (word_index == 0)
        {
            return "";
        }
        
        return strs[0].substr(0,word_index);
    }
};?

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        common_prefix = ''
        try: 
            for i in range(201):
                current_letter = strs[0][i]
                for string in strs:
                    if string[i] != current_letter:
                        return common_prefix
                common_prefix += current_letter
        except IndexError:
            return common_prefix

postado por @oxe em 22/02/2023 22:50

FlyCavok

Essa é a técnica do binary search, né? Li sobre ela esses dias, bem legal ver na prática

char * longestCommonPrefix(char ** strs, int strsSize){

    int i,j;
    int prefixSize = 0;
    int firstWordSize = strlen(strs[0]);
    char * prefix = malloc(sizeof(char)*(firstWordSize+1)); //+1 pra colocar o caractere de fim de string

    for(i=0;i<firstWordSize;i++)
        for(j=1;j<strsSize;j++)
            if(strs[j][i]!=strs[0][i]){
                prefixSize = i;
                i = firstWordSize +1;
                j = strsSize +1;
            }

    if(i==firstWordSize) //se chegou aqui eh pq a primeira palavra inteira eh prefixo valido
        prefixSize=firstWordSize;

    for(i=0;i<prefixSize;i++){ //copiando prefixo
        prefix[i]=strs[0][i];
    }

    prefix[prefixSize]=0; //colocando fim de string

    return prefix;
}?

postado por @oxe em 23/02/2023 10:17

maxete

malloc é pra separar memória, né?

No C os arrays funcionam como ponteiros? 

postado por @maxete em 23/02/2023 10:40

isso, malloc é de memory allocation. é para a gestão dinamica da memória.
Como o retorno é um char *, o formato que precisamos fazer é via malloc. Se eu criasse estaticamente o array, o tamanho tem que ser fixo (tipo 200 : char prefix[200]) e ao entregar o endereço surge o principal problema: ao criar o array no escopo local da função, depois de finalizada a função o setor de memoria utilizado é liberado para uso de qquer função, ou seja, não há aaaagarantia de integridade do ponteiro entregue.

Desta forma, você tem que separar (alocar) a memória deste array, que só vai liberar para uso quando você usar o "free".

Em C, os array são sempre trechos de memória contígua (o que não acontece com vectors do C++, por exemplo). quando vc usa o nome da variável do array sem o operador de acesso ao elemento "[i]", vc recebe o ponteiro do primeiro elemento.

prefix ---------------> ponteiro para o endereço da memória que começa o array

prefix+4*sizeof(char) -------------> ponteiro para o 5o elemento (endereço da memória + 4 elementos char pra frente)

prefix == &prefix[0] -----------------> mesma coisa
prefix+4*sizeof(char) == &prefix[4]   -------------------> mesma coisa

*prefix == prefix[0] ---------------> mesma coisa, conteúdo do endereço do ponteiro inicial do array

postado por @alyssoncs em 24/02/2023 22:04

Acho essa aqui bacaninha
LeetCode - The World's Leading Online Programming Learning Platform

Já me perguntaram em entrevista.

postado por @Giovanni em 24/02/2023 20:35

pessoal que tá participando, nada mais adequado do que ver com vocês o próximo desafio semanal

coloquem sugestões por favor
e uma questão média para gente lançar no desafio mensal

obrigado

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {       
        int inf = 0, sup = strs[0].size(); 

//inf representa o menor valor da posição do prefixo comum e sup
//representa o valor imediatamente acima ao maior que a posição
//pode assumir. Como inf é inicializado como 0, há uma ambiguidade
//que o algoritmo precisa levar em consideração
        
        while ((!(sup-inf == 1))||(inf == 0)){

//O algoritmo roda até que a posição esteja imediatamente abaixo da
//posição superior e inf seja diferente de 0 (devido à ambiguidade).
//Isso quer dizer que o while não quebra sozinho se o prefixo comum
//tiver exatamente uma letra (que corresponde à posição 0 no inf).
//Ou seja, é preciso haver uma quebra manual. 

            int length = inf+(sup-inf)/2+1;

//length indica o tamanho da substring que será comparada entre palavras.
//Ela é no mínimo igual a inf+1, pois as posições indicadas por inf
//são certas e não precisam mais ser comparadas. A adição de (sup-inf)/2
//indica que apenas os caracteres até a metade da zona de incerteza são
//comparados e, logo, length decresce exponencialmente (potência de 2)
//a cada iteração.
            
            for (int i = 0; i < strs.size(); i++){

//O tamanho de strs é o n° de palavras. Ou seja, itera 1 vez por palavra

                if (length > strs[i].size() || 
            strs[i].compare(inf, length-inf, strs[0], inf, length-inf) != 0){

//se length for maior que alguma das palavras ou se a substring comparada for
//distinta, então a maior posição do prefixo comum é menor que length
   
                    sup = length-1;

                    if (sup == 0){
                        return "";} 

//se sup chega a 0, significa que não há prefixo em comum 
                               
                    break;

//se houver alguma inconsistência, o for pode quebrar

                } else if (i+1 == strs.size()) {

//se chegar ao final do for sem inconsistência, então a substring comparada
//é comum a todas aa palavras. Ou seja, inf é no mínimo a posição indicada por
//length. Como as posições começam do 0 (um prefixo em comum de 2 corresponde à
//posição 1, por exemplo), é preciso reduzir 1 de length antes de igualar a inf
                    
                    inf = length-1;

                    if (inf == 0 && sup-inf == 1){

//se inf é zero depois do loop for, aignifica que já foi testada a posição 0 e
//nesse caso não há mais ambiguidade no valor de inf (ele indica que o prefixo
//comum é no mínimo igual a um caractere). Se além disso sup-inf é igual a 1,
//então inf não pode ser maior que 0 e o prefixo comum é de apenas 1 caractere.
//Em qualquer outra situação, inf necessariamente aumentará na execução do
//algoritmo, então este if é suficiente para remover a ambiguidade de inf e quebrar
//o while devidamente

                        return strs[0].substr(0,1);
                    }        
                }
            }            
        }

//retorna a substring formada por qualquer uma das palavras desde a posição inicial
//até a posição imediatamente anterior a sup. Poderia ser usado inf+1 igualmente.
//Não é possível usar length porque ela foi declarada dentro do while
           
        return strs[0].substr(0, sup);
    }
};

postado por @alyssoncs em 24/02/2023 22:04

Acho essa aqui bacaninha
LeetCode - The World's Leading Online Programming Learning Platform

Já me perguntaram em entrevista.

postado por @Rod100 em 25/02/2023 18:18

Sugestão para o próximo: LeetCode - The World's Leading Online Programming Learning Platform
problema fácil com a menor taxa de acerto

defmodule Solution do
  @spec longest_common_prefix(strs :: [String.t()]) :: String.t()
  def longest_common_prefix(strs) do
    shortest =
      strs
      |> Enum.sort_by(&String.length/1)
      |> List.first()

    max_length = String.length(shortest)

    codepoints = Enum.map(strs, &to_str_map(&1, max_length))

    shortest
    |> to_str_map(max_length)
    |> Enum.take_while(fn {idx, letter} -> Enum.all?(codepoints, &(&1[idx] == letter)) end)
    |> Enum.map(fn {_idx, letter} -> letter end)
    |> Enum.join("")
  end

  def to_str_map(str, max) do
    str |> String.codepoints() |> Enum.take(max) |> Enum.with_index(&{&2, &1}) |> Enum.into(%{})
  end
end