Find Words That Can Be Formed by Characters

🏠 ⬅️ ➡️

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = [ "cat ", "bt ", "hat ", "tree "], chars = "atach " Output: 6 Explanation: The strings that can be formed are "cat " and "hat " so the answer is 3 + 3 = 6.

Example 2:

Input: words = [ "hello ", "world ", "leetcode "], chars = "welldonehoneyr " Output: 10 Explanation: The strings that can be formed are "hello " and "world " so the answer is 5 + 5 = 10.

Constraints:

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

    integer :: i, j
    character(len=:), allocatable :: words(:)
    character(len=:), allocatable :: chars
    integer :: n_words, n_chars
    integer :: result

    ! read input
    read(*,*) n_words
    allocate(words(n_words))
    do i = 1, n_words
        read(*,*) words(i)
    end do
    read(*,*) n_chars
    allocate(chars(n_chars))
    do i = 1, n_chars
        read(*,*) chars(i)
    end do

    ! solve problem
    result = good_strings(words, chars)

    ! print output
    write(*,*) result

contains

    function good_strings(words, chars) result(sum)
        implicit none
        character(len=*), intent(in) :: words(:)
        character(len=*), intent(in) :: chars
        integer :: sum
        integer :: i, j

        sum = 0
        do i = 1, size(words)
            do j = 1, len(words(i))
                if (index(chars, words(i)(j:j)) /= 0) then
                    sum = sum + len(words(i))
                    exit
                end if
            end do
        end do
    end function good_strings

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

      integer :: i, j, k, l
      character(len=1000) :: words(1000)
      character(len=100) :: chars
      integer :: n, m
      integer :: count

      ! Read input
      read(*,*) n
      do i = 1, n
        read(*,*) words(i)
      end do
      read(*,*) chars
      read(*,*) m

      ! Initialize count
      count = 0

      ! Iterate over words
      do i = 1, n
        ! Iterate over characters in word
        do j = 1, len_trim(words(i))
          ! Check if character is in chars
          do k = 1, len_trim(chars)
            if (words(i)(j:j) == chars(k:k)) then
              ! Increment count if character is in chars
              count = count + 1
              exit
            end if
          end do
        end do
      end do

      ! Print output
      write(*,*) count

      end program solve
🌐 Data from online sources 
def num_tile_possibilities(tiles: str) -> int:
    freq = [0] * 26
    for c in tiles:
        freq[ord(c) - ord('A')] += 1

    def dfs(freq):
        result = 0
        for i in range(26):
            if freq[i] > 0:
                freq[i] -= 1
                result += 1 + dfs(freq)
                freq[i] += 1
        return result

    return dfs(freq)

First, calculate the frequency of each character in the input string tiles. Next, use depth-first search to explore all possible combinations of characters by decrementing the frequency of the current character, adding all the possible combinations for the remaining characters, and then restoring the frequency count for backtracking purposes. The final result will be the total count of all possible non-empty sequences.

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

int numTilePossibilities(std::string tiles) {
    std::vector<int> freq(26, 0);
    for (char c : tiles) {
        freq[c - 'A']++;
    }

    int result = 0;
    for (int i = 0; i < 26; i++) {
        if (freq[i]) {
            freq[i]--;
            result += 1 + numTilePossibilities(tiles);
            freq[i]++;
        }
    }
    return result;
}

First, calculate the frequency of each character in the input string tiles. Next, use depth-first search to explore all possible combinations of characters by decrementing the frequency of the current character, adding all the possible combinations for the remaining characters, and then restoring the frequency count for backtracking purposes. The final result will be the total count of all possible non-empty sequences.