Compruebe si las palabras están ordenadas según el nuevo orden de los alfabetos

Dada una secuencia de Palabras y el Orden del alfabeto. El orden del alfabeto es una permutación de letras minúsculas. La tarea es verificar si las palabras dadas están ordenadas lexicográficamente según el orden alfabético. Devuelva «Verdadero» si lo es, de lo contrario «Falso».

Ejemplos:

Entrada: Palabras = [“hello”, “leetcode”], Orden = “habcldefgijkmnopqrstuvwxyz”
Salida: verdadero

Entrada: Palabras = [“palabra”, “mundo”, “fila”], Orden = “abcworldefghijkmnpqstuvxyz”
Salida: falso
Explicación: Como ‘d’ viene después de ‘l’ en Orden, entonces palabras[0] > palabras[1] , por lo tanto, la secuencia no está ordenada.

Enfoque: Las palabras se ordenan lexicográficamente si y solo si se ordenan las palabras adyacentes. Esto se debe a que el orden es transitivo, es decir, si a <= b y b <= c, implica a <= c.

Entonces, nuestro objetivo es verificar si todas las palabras adyacentes a y b tienen a <= b.

Para verificar si para dos palabras adyacentes a y b, a <= b se cumple, podemos encontrar su primera diferencia. Por ejemplo, «visto» y «escena» tienen una primera diferencia de e y c. Después de esto, comparamos estos caracteres con el índice en orden.

Tenemos que lidiar con el carácter en blanco de manera efectiva. Si, por ejemplo, estamos comparando «agregar» con «adición», esta es una primera diferencia de (NULL) frente a «i».

A continuación se muestra la implementación del enfoque anterior:

# Function to check whether Words are sorted in given Order
def isAlienSorted(Words, Order):
    Order_index = {c: i for i, c in enumerate(Order)}
  
    for i in range(len(Words) - 1):
        word1 = Words[i]
        word2 = Words[i + 1]
  
        # Find the first difference word1[k] != word2[k].
        for k in range(min(len(word1), len(word2))):
  
            # If they compare false then it's not sorted.
            if word1[k] != word2[k]:
                if Order_index[word1[k]] > Order_index[word2[k]]:
                    return False
                break
        else:
  
            # If we didn't find a first difference, the
            # Words are like ("add", "addition").
            if len(word1) > len(word2):
                return False
  
    return True
  
  
# Program Code
Words = ["hello", "leetcode"]
Order = "habcldefgijkmnopqrstuvwxyz"
  
# Function call to print required answer
print(isAlienSorted(Words, Order))

True

Complejidad de tiempo: O(N), donde N es el número total de caracteres en todas las palabras.

Espacio Auxiliar: O(1)