Verifying an Alien Dictionary

🏠 ⬅️ ➡️

In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.

Example 1:

Input: words = [ "hello ", "leetcode "], order = "hlabcdefgijkmnopqrstuvwxyz " Output: true Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2:

Input: words = [ "word ", "world ", "row "], order = "worldabcefghijkmnpqstuvxyz " Output: false Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Example 3:

Input: words = [ "apple ", "app "], order = "abcdefghijklmnopqrstuvwxyz " Output: false Explanation: The first three characters "app " match, and the second string is shorter (in size.) According to lexicographical rules "apple " > "app ", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 20
  • order.length == 26
  • All characters in words[i] and order are English lowercase letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j
    character(len=26) :: order
    character(len=20), allocatable :: words(:)

    ! read input
    read(*,*) order
    allocate(words(size(order)))
    do i = 1, size(words)
        read(*,*) words(i)
    end do

    ! solve problem
    call solve(words, order)

contains

    subroutine solve(words, order)
        implicit none
        character(len=*), intent(in) :: words(:), order
        logical :: sorted

        sorted = .true.
        do i = 1, size(words)-1
            if (words(i+1) < words(i)) then
                sorted = .false.
                exit
            end if
        end do

        write(*,*) sorted

    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module main

implicit none

interface

function isAlienSorted(words, order) result(sorted)
    character(len=*), intent(in) :: words(:)
    character(len=*), intent(in) :: order
    logical :: sorted
end function isAlienSorted

end interface

contains

subroutine run()
    character(len=26) :: order
    character(len=*), parameter :: words(3) = ["hello ", "leetcode ", "word "]
    logical :: sorted

    ! Initialize the order of the alphabet
    order = "hlabcdefgijkmnopqrstuvwxyz "

    ! Check if the words are sorted in the alien language
    sorted = isAlienSorted(words, order)

    ! Print the result
    if (sorted) then
        print *, "The words are sorted in the alien language."
    else
        print *, "The words are not sorted in the alien language."
    end if

end subroutine run

function isAlienSorted(words, order) result(sorted)
    character(len=*), intent(in) :: words(:)
    character(len=*), intent(in) :: order
    logical :: sorted
    integer :: i, j, k

    ! Initialize the result
    sorted = .true.

    ! Check if the words are sorted lexicographically in the alien language
    do i = 1, size(words) - 1
        do j = 1, len_trim(words(i))
            do k = 1, len_trim(words(i + 1))
                if (words(i)(j:j) > words(i + 1)(k:k)) then
                    sorted = .false.
                    exit
                else if (words(i)(j:j) < words(i + 1)(k:k)) then
                    exit
                end if
            end do
            if (.not. sorted) exit
        end do
        if (.not. sorted) exit
    end do

end function isAlienSorted

end module main

! Test the function with the given examples
program test
    use main
    implicit none

    character(len=26) :: order
    character(len=*), parameter :: words(3) = ["hello ", "leetcode ", "word "]
    logical :: sorted

    ! Initialize the order of the alphabet
    order = "hlabcdefgijkmnopqrstuvwxyz "

    ! Check if the words are sorted in the alien language
    sorted = isAlienSorted(words, order)

    ! Print the result
    if (sorted) then
        print *, "The words are sorted in the alien language."
    else
        print *, "The words are not sorted in the alien language."
    end if

end program test
🌐 Data from online sources 
def reverse_string(s):
    return s[::-1]

The algorithm to reverse a string is simple. It takes the input string, iterates from the last character to the first, and appends each character to a new string, which is then returned.

In each of the provided implementations, the language's standard library, or a built-in method, is utilized to achieve the goal, rather than manually writing a loop to iterate over the string.

In C++, the std::reverse function from the <algorithm> library is used to reverse the input string.

In Java, a StringBuilder is created from the input string, and then its built-in reverse method is called. Finally, the reversed StringBuilder is converted back to a String.

In Python, slicing is used to reverse the string with the syntax s[::-1].

In JavaScript, the split method is used to convert the string into an array of characters. Then, the reverse method is called on the array, which reverses the order of the elements. Finally, the join method is called on the reversed array to convert it back to a string.

🌐 Data from online sources 
#include <string>
#include <algorithm>

std::string reverseString(const std::string& s) {
    std::string result = s;
    std::reverse(result.begin(), result.end());
    return result;
}

The algorithm to reverse a string is simple. It takes the input string, iterates from the last character to the first, and appends each character to a new string, which is then returned.

In each of the provided implementations, the language's standard library, or a built-in method, is utilized to achieve the goal, rather than manually writing a loop to iterate over the string.

In C++, the std::reverse function from the <algorithm> library is used to reverse the input string.

In Java, a StringBuilder is created from the input string, and then its built-in reverse method is called. Finally, the reversed StringBuilder is converted back to a String.

In Python, slicing is used to reverse the string with the syntax s[::-1].

In JavaScript, the split method is used to convert the string into an array of characters. Then, the reverse method is called on the array, which reverses the order of the elements. Finally, the join method is called on the reversed array to convert it back to a string.