Check If String Is a Prefix of Array

🏠 ⬅️ ➡️

Given a string s and an array of strings words, determine whether s is a prefix string of words.

A string s is a prefix string of words if s can be made by concatenating the first k strings in words for some positive k no larger than words.length.

Return true if s is a prefix string of words, or false otherwise.

Example 1:

Input: s = "iloveleetcode ", words = [ "i ", "love ", "leetcode ", "apples "] Output: true Explanation: s can be made by concatenating "i ", "love ", and "leetcode " together.

Example 2:

Input: s = "iloveleetcode ", words = [ "apples ", "i ", "love ", "leetcode "] Output: false Explanation: It is impossible to make s using a prefix of arr.

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 20
  • 1 <= s.length <= 1000
  • words[i] and s consist of only lowercase English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=:), allocatable :: s, word
    character(len=:), dimension(:), allocatable :: words
    logical :: is_prefix
    integer :: i, k

    ! Example 1
    allocate(character(len=4) :: s)
    s = "ilove"
    allocate(character(len=5) :: word)
    word = "i "
    allocate(character(len=6) :: word2)
    word2 = "love "
    allocate(character(len=9) :: word3)
    word3 = "leetcode "
    allocate(character(len=7) :: word4)
    word4 = "apples "
    allocate(character(len=8) :: words(4))
    words(1) = word
    words(2) = word2
    words(3) = word3
    words(4) = word4
    is_prefix = is_prefix_string(s, words)
    print '(L1)', is_prefix

    ! Example 2
    deallocate(s)
    allocate(character(len=4) :: s)
    s = "ilove"
    deallocate(word)
    deallocate(word2)
    deallocate(word3)
    deallocate(word4)
    allocate(character(len=6) :: word)
    word = "apples "
    allocate(character(len=7) :: word2)
    word2 = "i "
    allocate(character(len=6) :: word3)
    word3 = "love "
    allocate(character(len=9) :: word4)
    word4 = "leetcode "
    allocate(character(len=8) :: words(4))
    words(1) = word
    words(2) = word2
    words(3) = word3
    words(4) = word4
    is_prefix = is_prefix_string(s, words)
    print '(L1)', is_prefix

contains

    function is_prefix_string(s, words) result(is_prefix)
        implicit none
        character(len=*), intent(in) :: s
        character(len=*), dimension(:), intent(in) :: words
        logical :: is_prefix
        integer :: i, k

        do k = 1, size(words)
            is_prefix = .true.
            do i = 1, k
                if (s /= words(i)(1:len_trim(s))) then
                    is_prefix = .false.
                    exit
                end if
            end do
            if (is_prefix) exit
        end do
    end function is_prefix_string

end program main
✅ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: i, j, k, len
character(len=1000) :: s
character(len=20), dimension(100) :: words
logical :: is_prefix

! Read input
read(*,*) s
read(*,*) words

! Initialize variables
is_prefix = .false.
len = len_trim(s)

! Check if s is a prefix of words
do i = 1, len
    do j = 1, size(words)
        if (s(i:i+len_trim(words(j))) == words(j)) then
            k = k + 1
            exit
        end if
    end do
    if (k > size(words)) then
        exit
    end if
end do

! Check if k is less than or equal to the length of words
if (k <= size(words)) then
    is_prefix = .true.
end if

! Output result
write(*,*) is_prefix

end
🌐 Data from online sources 
def max_ice_cream(costs, coins):
    costs.sort()
    count = 0
    for cost in costs:
        if coins >= cost:
            coins -= cost
            count += 1
        else:
            break
    return count

The algorithm first sorts the costs array in ascending order. Then, it traverses the sorted array and checks if the current cost can be covered by the remaining coins. If it can, the function decreases the coins by the cost and increments the count of bought ice cream bars. If it can't, the loop breaks, as the remaining ice creams are all more expensive. Finally, the function returns the count of bought ice cream bars.

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

int maxIceCream(std::vector<int>& costs, int coins) {
    std::sort(costs.begin(), costs.end());
    int count = 0;
    for (int cost : costs) {
        if (coins >= cost) {
            coins -= cost;
            count++;
        } else {
            break;
        }
    }
    return count;
}

The algorithm first sorts the costs array in ascending order. Then, it traverses the sorted array and checks if the current cost can be covered by the remaining coins. If it can, the function decreases the coins by the cost and increments the count of bought ice cream bars. If it can't, the loop breaks, as the remaining ice creams are all more expensive. Finally, the function returns the count of bought ice cream bars.