String Matching in an Array

🏠 ⬅️ ➡️

Given an array of string words, return all strings in words that is a substring of another word. You can return the answer in any order.

A substring is a contiguous sequence of characters within a string

Example 1:

Input: words = [ "mass ", "as ", "hero ", "superhero "] Output: [ "as ", "hero "] Explanation: "as " is substring of "mass " and "hero " is substring of "superhero ". [ "hero ", "as "] is also a valid answer.

Example 2:

Input: words = [ "leetcode ", "et ", "code "] Output: [ "et ", "code "] Explanation: "et ", "code " are substring of "leetcode ".

Example 3:

Input: words = [ "blue ", "green ", "bu "] Output: [] Explanation: No string of words is substring of another string.

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 30
  • words[i] contains only lowercase English letters.
  • All the strings of words are unique.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 4
    character(len=30), dimension(n) :: words
    character(len=30), allocatable, dimension(:) :: substrs
    integer :: i, j

    ! Example 1
    words(1) = 'mass '
    words(2) = 'as '
    words(3) = 'hero '
    words(4) = 'superhero '

    call get_substrs(words, substrs)
    do i = 1, size(substrs)
        write(*,*) trim(substrs(i))
    end do

    ! Example 2
    words(1) = 'leetcode '
    words(2) = 'et '
    words(3) = 'code '

    call get_substrs(words, substrs)
    do i = 1, size(substrs)
        write(*,*) trim(substrs(i))
    end do

    ! Example 3
    words(1) = 'blue '
    words(2) = 'green '
    words(3) = 'bu '

    call get_substrs(words, substrs)
    if (size(substrs) > 0) then
        do i = 1, size(substrs)
            write(*,*) trim(substrs(i))
        end do
    else
        write(*,*) 'No substring found'
    end if

contains

    subroutine get_substrs(words, substrs)
        implicit none
        character(len=*), intent(in) :: words(:)
        character(len=*), allocatable, intent(out) :: substrs(:)
        integer :: i, j, k, l
        logical :: found

        allocate(substrs(0))

        do i = 1, size(words) - 1
            do j = i + 1, size(words)
                found = .false.
                do k = 1, len(words(j))
                    do l = 1, len(words(i))
                        if (words(j)(k:k) == words(i)(l:l)) then
                            found = .true.
                            exit
                        end if
                    end do
                    if (found) exit
                end do
                if (found) then
                    allocate(character(len=len(words(i))) :: substrs(size(substrs)+1))
                    substrs(size(substrs)) = words(i)
                end if
            end do
        end do
    end subroutine get_substrs

end program main
✅ Compiled
❌ Executed
❌ Correct 
program substring_strings
      implicit none

      integer, parameter :: MAX_WORDS = 100
      integer, parameter :: MAX_LENGTH = 30

      character(len=MAX_LENGTH), dimension(MAX_WORDS) :: words
      character(len=MAX_LENGTH), dimension(MAX_WORDS) :: substring_words
      integer :: num_words, i, j, k

      ! Read the input
      read(*,*) num_words
      do i = 1, num_words
        read(*,*) words(i)
      end do

      ! Initialize the output array
      substring_words = ""

      ! Loop through each word and check if it is a substring of another word
      do i = 1, num_words
        do j = i + 1, num_words
          if (index(words(j), words(i)) /= 0) then
            ! The word at index j is a substring of the word at index i
            substring_words(k) = words(j)
            k = k + 1
          end if
        end do
      end do

      ! Print the output
      do i = 1, k - 1
        write(*,*) substring_words(i)
      end do

      end program substring_strings
🌐 Data from online sources 
import math

def smallest_divisor(nums, threshold):
    left, right = 1, 10**6
    while left < right:
        mid = (left + right) // 2
        total = sum(math.ceil(n / mid) for n in nums)
        if total > threshold:
            left = mid + 1
        else:
            right = mid
    return left

We will use a binary search to find the smallest divisor. Define the search range initially from 1 to 1,000,000 (10^6). Calculate the middle value 'mid' between the given search range (left and right), and then get the sum of division results using that middle value in the array. If the sum of the division results is greater than the given threshold, that means the divisor must be larger, so we update the left boundary to be equal to 'mid' + 1. If the sum is less than or equal to the threshold, it means the divisor can be smaller or the value itself, so we update the right boundary to be equal to 'mid'. We repeat this process until the left and right boundaries are equal, and the final answer will be the left boundary.

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

int smallestDivisor(std::vector<int>& nums, int threshold) {
    int left = 1, right = 1e6;
    while (left < right) {
        int mid = (left + right) / 2;
        int sum = 0;
        for (int n : nums) {
            sum += std::ceil(1.0 * n / mid);
        }
        if (sum > threshold) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

We will use a binary search to find the smallest divisor. Define the search range initially from 1 to 1,000,000 (10^6). Calculate the middle value 'mid' between the given search range (left and right), and then get the sum of division results using that middle value in the array. If the sum of the division results is greater than the given threshold, that means the divisor must be larger, so we update the left boundary to be equal to 'mid' + 1. If the sum is less than or equal to the threshold, it means the divisor can be smaller or the value itself, so we update the right boundary to be equal to 'mid'. We repeat this process until the left and right boundaries are equal, and the final answer will be the left boundary.