BastterCode semana 6 - HashMaps - Word Pattern (290)
comentada em 12/03/2023 00:19

A explicação do problema diz que é pra ter uma bijeção entre as letras de pattern e as palavras não-vazias de s.

Pra quem não entendeu, bijeção ou função bijetora é a função injetora e sobrejetora ao mesmo tempo. Ou seja, é aquela que só dá um resultado pra cada input (como toda função), os resultados não são iguais para inputs diferentes (injeção) e todos os outputs possíveis têm um input (sobrejeção).

Ou seja, se o padrão for "abba", precisamos ter quatro palavras não-vazias em s, que se assONcia a cada letra do padrão. Ou seja, a primeira palavra de s se assONcia a "a", a segunda se assONcia a "b", a terceira se assONcia a "b" e a quarta se assONcia a "a". As palavras que se assONciam a "a" precisam ser iguais, assim como as que se assONciam a "b".

Se uma mesma palavra se assONciar a "a" e a "b", a função não é injetiva, logo não é uma bijeção. Se houver mais palavras em s do que letras em padrão, então vai ficar sobrando palavra sem assONciação com letra e a função não seria sobrejetora, logo não seria uma bijeção. E se uma mesma letra de padrão se assONciar a mais de uma palavra de s, então não seria uma função, logo não seria uma bijeção. 

postado por @Giovanni em 13/02/2023 11:21

Aproveitando o sucesso de semana passada, o que acham do primeiro desafio mensal ser um mais avançado de matrizes, tipo esse?

LeetCode - The World's Leading Online Programming Learning Platform

Eu topo. Só seria legal ter um banner pro desafio mensal também, pois do contrário o tópico vai ficar difícil de achar depois de uns dias. 

kotlin

Dart

class Solution {
  bool wordPattern(String pattern, String s) {
    var lst = s.split(' ');
    Map<String, String?> patternMap = {};
    Map<String, String?> wordMap = {};

    if (lst.length != pattern.length) return false;

    for (int i = 0; i < lst.length; i++) {
      String word = lst[i];
      String patternChar = pattern[i];

      if (wordMap[word] == null && patternMap[patternChar] == null) {
        patternMap[patternChar] = word;
        wordMap[word] = patternChar;
      } else {
        if (wordMap[word] != patternChar || patternMap[patternChar] != word)
          return false;
      }
    }
    return true;
  }
}

class Solution {
    fun wordPattern(pattern: String, s: String): Boolean {
        val sList = s.split(" ")
        if (sList.size != pattern.length) return false

        var dictA = mutableMapOf<Char, String>()
        for (i in sList.indices){
            println("item number $i")
            if (dictA.containsKey(pattern[i])){
                println("contains key ${pattern[i]}")
                if (dictA[pattern[i]] != sList[i]){
                    println("value in item number $i does not match existing dict key")
                    return false
                }
                else {
                    println ("value matches with key")
                    continue
                }
            }
            else if (dictA.containsValue(sList[i])){
                println("existing value, but theres no key")
                return false
            }
            println("key and value do not exist, adding new entry (${pattern[i]}, ${sList[i]})")
            dictA[pattern[i]] = sList[i]
        }
        //return true
        println("resulting true dictionary is:")
        println(dictA)

        return true
    }
}

Aparência feia, mas saiu depois de um dia longo de trabalho...

Go, esse código não ficava bonito de jeito nenhum haha

versão melhorada e supercomentada, em kotlin:

class Solution {
    fun wordPattern(pattern: String, s: String): Boolean {
// Primeira coisa a fazer: quebrar o string de palavras s em
// uma lista de strings, cada item da lista é uma palavra no
// string s. O ponto de quebra é o caracter espaço " ".
        val sList = s.split(" ")
        
// Cada letra em pattern tem uma palavra assONciada, abaixo
// verifica-se se o número de palavras é igual ao de letras,
// caso negativo a função já devolve falso e nem continua.
        if (sList.size != pattern.length) return false

// cria uma variável map para armazenar a correspondência entre
// cada caracter em pattern e cada palavra em sList
        var map = mutableMapOf<Char, String>()
        
// iteração para cada uma das palavras (também podia ser para
// cada um dos caracteres, já que são em mesmo número)
        for (i in sList.indices){
// se o enésimo caracter já existir armazenado em map...
            if (map.containsKey(pattern[i])){
// temos que verificar se a enésima palavra correponde
// ao que já foi armazenado em map. Caso correto 'continue'
// para próxima iteração do for
                if (map[pattern[i]] == sList[i]) continue
// Caso incorreto retorna false e pára função
                else return false
            }
// else if, ou seja, o caracter nunca foi armazenado em map,
// espera-se que a palavra também não tenha sido armazenada.
// Se existir a palavra deve retornar false
            else if (map.containsValue(sList[i])) return false
            
// se chegou aqui é porque o enésimo caracter e a enésima
// palavra não existem em map e devem ser acrescentadas a
// map para verificações nas próximas iterações do for
            map[pattern[i]] = sList[i]
        }
// se passou pelo for sem ser identificado como false, é porque
// é true, então retorna true.
        return true
    }
}

Ver mais


Ver mais

Aproveitei pra estudar maps e sets, conceitos que não tinham no tutorial que eu usei pra aprender C++.

Coloquei explicação na imagem, pra quem tiver interesse

C#

public class Solution {
    public bool WordPattern(string pattern, string s) {
        //copiei a ideia central de uma outra solução
        //mas a versão aqui está um pouco diferente
        //resolvi estudar ela e explicar detalhadamente
        //pois era mais simples e eficiente do que a
        //solução que eu havia elaborado
        //acredito que seja bom
        //para treinar leitura de códigos escritos
        //por outras pessoas

        //a cada possível condição que invalide já retorna falso
        //caso nenhuma condição invalide retorna verdadeiro

        //armazena cada palavra da string em uma lista
        var wordList = s.Split(' ');
        
        //verifica se há a mesma quantidade de palavras 
        //na string e quantidade de letras no padrão
        //invalida o resultado
        if (pattern.Length != wordList.Length) return false;

        //Em c# o equivalente a um hashmap é um Dictionary
        var wordDict = new Dictionary<char, string>();
        
        //Percorre cada letra do padrão
        for (var i = 0; i < pattern.Length; i++) {
            
            //a primeira iteração vai sempre direto
            //para o else, adicionando a palavra
            //e a chave no dicionário

            //verifica se a letra do contador aparece como Key
            if (wordDict.ContainsKey(pattern[i]))
            {
                //caso o dicionário não contenha
                //a palavra atual
                //invalida o resultado
                if (wordList[i] != wordDict[pattern[i]]) return false;
            }
            else
            {
                //caso apareça o valor repetido para
                //para duas letras chave diferentes
                //invalida o resultado
                if (wordDict.ContainsValue(wordList[i])) return false; 
                
                //armazena a letra do padrão e a palavra
                wordDict.Add(pattern[i], wordList[i]);
            }
        }

        //caso não tenha retornado anteriormente
        //chega aqui, considerando válido
        return true;
    }
}

Uma solução alternativa, que usa funções da biblioteca de string do C++ e roda apenas no tamanho de pattern (que é até 10x menor que s).

Usei um XOR para testar a condição no primeiro if do for. O XOR retorna verdadeiro se uma, e apenas uma, das duas proposições for verdadeira.

No caso específico, as duas proposições dentro do XOR são: 1- se a variável que aponta a posição para o final da palavra retorna nulo (o que indica que é a última palavra de s); e 2- se o tamanho de pattern menos o iterador i for 1 (o que indica que esse é o último laço do for e, consequentemente, o último caractere de pattern).

Se as duas condições forem verdadeiras, então o último caractere de pattern corresponde à última palavra de s, o que é ok. Se as duas condições forem falsas, então ainda falta caractere em pattern e ainda falta palavra em s, o que é ok.

Mas se apenas uma das duas for verdadeira, significa que ou tem caractere sobrando em pattern, ou tem palavra sobrando em s, o que significa que a função não é bijetora.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        pattern_letters = list(pattern)
        words = s.split(' ')
        
        n_patterns = len(pattern_letters)
        n_words = len(words)
        
        if n_patterns != n_words or n_patterns == 0 or n_words == 0:
            return False

        map_ = {}
        for letter, word in zip(pattern_letters, words):
            if letter not in map_.keys() and word not in map_.values():
                map_[letter] = word
            elif map_.get(letter) != word:
                return False
            else:
                continue
        return True

Ver mais

@oxe isso sim é aprender rápido. O cara olha 1 solução bitwise e já mete um XOR na seguinte hahaha

Boa oxe!

@FlyCavok

Kkkk eu fui estudar, né. Não foi só bater o olho kkk

Estudar programação tem sido meu hobby essas últimas semanas por causa desses desafios. Tô gostando bastante, acho até que vou começar a comprar livros/cursos. 

Uma última versão, quase igual à anterior. Agora usando stringstream, uma ferramenta do C++ que permite trabalhar com strings como um stream de valores.

Basicamente, ela separa a string, contando um valor para cada conjunto de caracteres entre um espaço e outro, o que permite extrair esses valores para uma outra variável e, se necessário, transformar os valores em inteiros, booleans ou outros tipos.

Usar o stringstream me permite eliminar algumas variáveis que eram necessárias para identificar o início e o fim de cada palavra em s e deixa o código mais bonitinho

A função eof (end of file) retorna verdadeiro se já chegou ao fim do stream, ou seja, cumpre a mesma função no XOR que comparar a função find com o npos (que indica o fim da string).

Java

class Solution {
 public boolean wordPattern(String pattern, String s) {
    if (pattern == null || s == null) {
      return false;
    }

    var wordPieces = s.split(" ");

    if (pattern.length() != wordPieces.length) {
      return false;
    }

    final var wordMap = new HashMap<Character, String>();
    for (int i = 0; i < wordPieces.length; i++) {
      if (!wordMap.containsValue(wordPieces[i])) {
        wordMap.putIfAbsent(pattern.charAt(i), wordPieces[i]);
      }
      if ( !wordMap.containsKey(pattern.charAt(i)) || !wordMap.get(pattern.charAt(i)).equals(wordPieces[i])) {
        return false;
      }
    }

    return true;
  }

}

Ver mais

Impressionante como esse negócio consome memória.

Este desafio me empurrou para aprender Kotlin. Quem se interessar, sugiro o "Kotlin bootcamp" da google, tem todo o passo a passo indicando o que instalar no computador e o básico da linguagem. Quem não quiser passar por toda instalação, consegue testar on-line no website kotlin playground.

No curso do bootcamp ontem passei pela expressão "when", equivalente ao "switch" do C++ e outros, daí voltei a este desafio e dei uma limpada nos ifs, resultado abaixo:

class Solution {
    fun wordPattern(pattern: String, s: String): Boolean {
        // quebra o string s em uma lista de palavras
        val sList = s.split(" ")
        
        // Checa se número de caracteres = número de palavras
        if (sList.size != pattern.length) return false

        // cria uma variável map para armazenar a correspondência entre
        // cada caracter em pattern e cada palavra em sList
        var map = mutableMapOf<Char, String>()
        
        // iteração para cada uma das palavras
        for (i in sList.indices){
            when {
                // se o enésimo caracter já existir armazenado em map E a palavra assONciada
                // for diferente da do mapa deve retornar falso.
                (map.containsKey(pattern[i])) && (map[pattern[i]] != sList[i]) -> return false
                // se o enésimo caracter não existir no map E a enésima palavra já existir
                // no map
                (!map.containsKey(pattern[i])) && (map.containsValue(sList[i])) -> return false
            }

            // o par de caracter e palavra são adicionados ao map
            map[pattern[i]] = sList[i]
        }
		// se passou pelo for sem ser identificado como false, é porque
		// é true, então retorna true.
        return true
    }
}?

Estou tão enrolado de tempo que quase não consegui fazer o dessa semana.
 

# O código

def word_pattern(pattern, s)
  pattern_as_ary = pattern.split('')
  s_as_ary       = s.split(' ')

  return false if pattern_as_ary.size != s_as_ary.size

  pattern_and_s  = {}

  answer = true
  s_as_ary.each_with_index do |word, index|
    pattern_letter = pattern_as_ary[index]
    word_by_pattern = nil

    if pattern_and_s.key(word).nil? && !pattern_and_s.keys.include?(pattern_letter)
      pattern_and_s[pattern_letter] = word
    end
    word_by_pattern = pattern_and_s[pattern_letter]
    
    answer = answer && word == word_by_pattern
  end

  return answer
end

## A linha de raciocínio
1. Separa o pattern e a string a ser testada em uma lista(array). A lista derivada do parâmetro pattern é um elemento da lista por letra. A lista derivada do parâmetro s usou o espaço em branco como delimitador de elementos.

    Daí que "abba" vira a lista ["a", "b", "b", "a"]
    E, "dog cat cat dog" vira a lista ["dog", "cat", "cat", "dog"]
2. Se o tamanho das listas for diferentes, já retorna false
3. Crio a variável booleana com a resposta, chamada answer. E, inicializo como verdadeiro.
4. Para cada palavra na lista de palavras(a lista criada a partir do parâmetro s)
4.1 Eu pego a letra que é o elemento na mesma posição na lista de letras(criada a partir do parâmetro pattern)
4.2 Se eu ainda não associei essa letra a uma palavra eu assONcio agora. E, guardo o valor na lista de assONciação(Map) chamado pattern_and_s. Essa lista é uma estrutura de dado que contem uma chave assONciada a um valor. Se você tenta atribuir a mesma chave a outro valor ele não adiciona a chave duas vezes, como nas listas, ele substitui o valor atual da chave.
    Daí que eu tenho {"a" => "dog", "b" => "cat"}
4.3 Guardo na variável word_by_pattern a palavra assONciada com a letra pega no passo 4.1
4.4 Parecido com a idéia de reduce eu vou atualizando o valor de answer. Eu valido que a palavra atual é igual a palavra que eu adicionei na lista de assONciação. Quando estiver diferente é porque a segunda string não segue o padrão da primeira.
5. Retorno o valor atual de answer
# O Resultado


Ver mais

 

postado por @Abra em 18/02/2023 16:27

Estou tão enrolado de tempo que quase não consegui fazer o dessa semana.
 

# O código

def word_pattern(pattern, s)
  pattern_as_ary = pattern.split('')
  s_as_ary       = s.split(' ')

  return false if pattern_as_ary.size != s_as_ary.size

  pattern_and_s  = {}

  answer = true
  s_as_ary.each_with_index do |word, index|
    pattern_letter = pattern_as_ary[index]
    word_by_pattern = nil

    if pattern_and_s.key(word).nil? && !pattern_and_s.keys.include?(pattern_letter)
      pattern_and_s[pattern_letter] = word
    end
    word_by_pattern = pattern_and_s[pattern_letter]
    
    answer = answer && word == word_by_pattern
  end

  return answer
end

## A linha de raciocínio
1. Separa o pattern e a string a ser testada em uma lista(array). A lista derivada do parâmetro pattern é um elemento da lista por letra. A lista derivada do parâmetro s usou o espaço em branco como delimitador de elementos.

    Daí que "abba" vira a lista ["a", "b", "b", "a"]
    E, "dog cat cat dog" vira a lista ["dog", "cat", "cat", "dog"]
2. Se o tamanho das listas for diferentes, já retorna false
3. Crio a variável booleana com a resposta, chamada answer. E, inicializo como verdadeiro.
4. Para cada palavra na lista de palavras(a lista criada a partir do parâmetro s)
4.1 Eu pego a letra que é o elemento na mesma posição na lista de letras(criada a partir do parâmetro pattern)
4.2 Se eu ainda não associei essa letra a uma palavra eu assONcio agora. E, guardo o valor na lista de assONciação(Map) chamado pattern_and_s. Essa lista é uma estrutura de dado que contem uma chave assONciada a um valor. Se você tenta atribuir a mesma chave a outro valor ele não adiciona a chave duas vezes, como nas listas, ele substitui o valor atual da chave.
    Daí que eu tenho {"a" => "dog", "b" => "cat"}
4.3 Guardo na variável word_by_pattern a palavra assONciada com a letra pega no passo 4.1
4.4 Parecido com a idéia de reduce eu vou atualizando o valor de answer. Eu valido que a palavra atual é igual a palavra que eu adicionei na lista de assONciação. Quando estiver diferente é porque a segunda string não segue o padrão da primeira.
5. Retorno o valor atual de answer
# O Resultado


Ver mais

 

Pequena melhoria:

Na linha 19, caso você atribua "False" para o answer, você não precisa mais verificar o resto, porque jamais voltará a ser "True".
Então você pode retornar o resultado. "False" logo e evitar iterações desnecessárias.

postado por @adicionado em 19/02/2023 11:10

postado por Abra em 18/02/2023 16:27.
 
# O código

    answer = answer && word == word_by_pattern    answer = answer && word == word_by_pattern

Pequena melhoria:

Na linha 19, caso você atribua "False" para o answer, você não precisa mais verificar o resto, porque jamais voltará a ser "True".
Então você pode retornar o resultado. "False" logo e evitar iterações desnecessárias.

Eu tenho a impressão que eu poderia trocar por algo como:

return false if word != word_by_pattern.

O que removeria a necessidade da variável answer.

Mas, não consegui testar, ainda.