Check If a Word Occurs As a Prefix of Any Word in a Sentence

🏠 ⬅️ ➡️

Given a sentence that consists of some words separated by a single space, and a searchWord, check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence (1-indexed) where searchWord is a prefix of this word. If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

A prefix of a string s is any leading contiguous substring of s.

Example 1:

Input: sentence = "i love eating burger ", searchWord = "burg " Output: 4 Explanation: "burg " is prefix of "burger " which is the 4th word in the sentence.

Example 2:

Input: sentence = "this problem is an easy problem ", searchWord = "pro " Output: 2 Explanation: "pro " is prefix of "problem " which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3:

Input: sentence = "i am tired ", searchWord = "you " Output: -1 Explanation: "you " is not a prefix of any word in the sentence.

Constraints:

  • 1 <= sentence.length <= 100
  • 1 <= searchWord.length <= 10
  • sentence consists of lowercase English letters and spaces.
  • searchWord consists of lowercase English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=100) :: sentence
    character(len=10) :: searchWord
    integer :: i, j, idx, minIdx
    logical :: found

    ! Example 1
    sentence = "i love eating burger "
    searchWord = "burg "
    write(*,*) 'Example 1:'
    write(*,*) 'Input: ', trim(sentence), ', ', trim(searchWord)
    idx = findPrefixIndex(sentence, searchWord)
    write(*,*) 'Output: ', idx

    ! Example 2
    sentence = "this problem is an easy problem "
    searchWord = "pro "
    write(*,*) 'Example 2:'
    write(*,*) 'Input: ', trim(sentence), ', ', trim(searchWord)
    idx = findPrefixIndex(sentence, searchWord)
    write(*,*) 'Output: ', idx

    ! Example 3
    sentence = "i am tired "
    searchWord = "you "
    write(*,*) 'Example 3:'
    write(*,*) 'Input: ', trim(sentence), ', ', trim(searchWord)
    idx = findPrefixIndex(sentence, searchWord)
    write(*,*) 'Output: ', idx

contains

    function findPrefixIndex(sentence, searchWord) result(idx)
        implicit none
        character(len=*), intent(in) :: sentence
        character(len=*), intent(in) :: searchWord
        integer :: idx
        logical :: found

        idx = -1
        found = .false.
        do i = 1, size(sentence)
            if (sentence(i:i+size(searchWord)-1) == searchWord) then
                found = .true.
                idx = i
                exit
            end if
        end do

        if (.not. found) then
            idx = -1
        end if
    end function findPrefixIndex
end program main
✅ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: sentence_length, search_word_length, i, j, min_index, index
character(len=100) :: sentence, search_word
logical :: found

! Read input
read(*,*) sentence
read(*,*) search_word

! Initialize variables
sentence_length = len_trim(sentence)
search_word_length = len_trim(search_word)
min_index = 100
found = .false.

! Loop through words in sentence
do i = 1, sentence_length
    ! Check if current word is a prefix of search word
    if (sentence(i:i+search_word_length-1) == search_word) then
        ! If so, update minimum index
        min_index = min(min_index, i)
        found = .true.
    end if
end do

! Output result
if (found) then
    write(*,*) min_index
else
    write(*,*) -1
end if

end
🌐 Data from online sources 
def filter_restaurants(restaurants, vegan_friendly, max_price, max_distance):
    def custom_compare(a, b):
        if a[1] == b[1]:
            return b[0] - a[0]
        return b[1] - a[1]

    filtered_restaurants = [
        r for r in restaurants
        if (vegan_friendly == 0 or r[2] == vegan_friendly) and r[3] <= max_price and r[4] <= max_distance
    ]

    filtered_restaurants.sort(key=lambda r: (r[1], r[0]), reverse=True)

    return [r[0] for r in filtered_restaurants]

The algorithm filters the given restaurants by checking each restaurant's vegan-friendly status, price, and distance. If the veganFriendly input is 0, the restaurant is considered regardless of its vegan-friendly status. If it is 1, only those restaurants with a vegan-friendly status of 1 are considered. Additionally, the restaurant's price and distance must be less than or equal to the given maxPrice and maxDistance, respectively. After filtering, the restaurants are sorted based on their ratings in descending order, and if two restaurants have the same rating, they are sorted by their IDs in descending order. Finally, the list of restaurant IDs is returned.

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

using namespace std;

bool customCompare(vector<int>& a, vector<int>& b) {
    if (a[1] == b[1]) return a[0] > b[0];
    return a[1] > b[1];
}

vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
    vector<vector<int>> filteredRestaurants;
    for (auto& r : restaurants) {
        if ((veganFriendly == 0 || r[2] == veganFriendly) && r[3] <= maxPrice && r[4] <= maxDistance) {
            filteredRestaurants.push_back(r);
        }
    }
    sort(filteredRestaurants.begin(), filteredRestaurants.end(), customCompare);
    vector<int> ids;
    for (auto& r : filteredRestaurants) {
        ids.push_back(r[0]);
    }
    return ids;
}

The algorithm filters the given restaurants by checking each restaurant's vegan-friendly status, price, and distance. If the veganFriendly input is 0, the restaurant is considered regardless of its vegan-friendly status. If it is 1, only those restaurants with a vegan-friendly status of 1 are considered. Additionally, the restaurant's price and distance must be less than or equal to the given maxPrice and maxDistance, respectively. After filtering, the restaurants are sorted based on their ratings in descending order, and if two restaurants have the same rating, they are sorted by their IDs in descending order. Finally, the list of restaurant IDs is returned.