Given a string text and an array of strings words, return an array of all index pairs [i, j] so that the substring text[i...j] is in words.
Return the pairs [i, j] in sorted order (i.e., sort them by their first coordinate, and in case of ties sort them by their second coordinate).
Example 1:
Input: text = "thestoryofleetcodeandme ", words = [ "story ", "fleet ", "leetcode "] Output: [[3,7],[9,13],[10,17]]
Example 2:
Input: text = "ababa ", words = [ "aba ", "ab "] Output: [[0,1],[0,2],[2,3],[2,4]] Explanation: Notice that matches can overlap, see "aba " is found in [0,2] and [2,4].
Constraints:
1 <= text.length <= 1001 <= words.length <= 201 <= words[i].length <= 50text and words[i] consist of lowercase English letters.words are unique.program main
implicit none
character(len=100) :: text
character(len=50), dimension(:), allocatable :: words
integer, dimension(:,:), allocatable :: indices
integer :: i, j, n, m
! Example 1
text = 'thestoryofleetcodeandme '
allocate(character(len=50) :: words(3))
words(1) = 'story '
words(2) = 'fleet '
words(3) = 'leetcode '
call solve(text, words, indices)
do i = 1, size(indices, 1)
write(*,'(A,I0,A,I0)') '[', indices(i,1), ',', indices(i,2), ']'
end do
! Example 2
text = 'ababa '
allocate(character(len=50) :: words(4))
words(1) = 'aba '
words(2) = 'ab '
words(3) = 'ba '
words(4) = 'a '
call solve(text, words, indices)
do i = 1, size(indices, 1)
write(*,'(A,I0,A,I0)') '[', indices(i,1), ',', indices(i,2), ']'
end do
contains
subroutine solve(text, words, indices)
implicit none
character(len=*), intent(in) :: text
character(len=*), dimension(:), intent(in) :: words
integer, dimension(:,:), intent(out) :: indices
integer :: i, j, k, l, n, m
n = len(text)
m = size(words)
allocate(indices(m,2))
do i = 1, m
do j = 1, n-len(words(i))+1
do k = 1, len(words(i))
if (text(j+k-1:j+k-1) /= words(i)(k:k)) exit
end do
if (k == len(words(i)+1)) then
indices(i,1) = j
indices(i,2) = j + len(words(i)) - 1
exit
end if
end do
end do
indices = transpose(indices)
indices = merge(indices, -1, indices(:,1) < indices(:,2))
indices = merge(indices, -1, indices(:,1) == indices(:,2))
indices = merge(indices, -1, indices(:,1) > indices(:,2))
end subroutine solve
end program maintemp.f95:43:17:
43 | allocate(indices(m,2))
| 1
Error: Allocate-object at (1) must be ALLOCATABLE or a POINTER
temp.f95:50:29:
50 | if (k == len(words(i)+1)) then
| 1
Error: Operands of binary numeric operator ‘+’ at (1) are CHARACTER(*)/INTEGER(4)
temp.f95:59:24:
59 | indices = merge(indices, -1, indices(:,1) < indices(:,2))
| 1
Error: Incompatible ranks in arguments 'tsource' and 'mask' for intrinsic 'merge' (2 and 1) at (1)
temp.f95:60:24:
60 | indices = merge(indices, -1, indices(:,1) == indices(:,2))
| 1
Error: Incompatible ranks in arguments 'tsource' and 'mask' for intrinsic 'merge' (2 and 1) at (1)
temp.f95:61:24:
61 | indices = merge(indices, -1, indices(:,1) > indices(:,2))
| 1
Error: Incompatible ranks in arguments 'tsource' and 'mask' for intrinsic 'merge' (2 and 1) at (1)
module match_words
implicit none
contains
function match_words_brute_force(text, words) result(matches)
! Brute force solution
character(len=*), intent(in) :: text
character(len=*), intent(in) :: words(:)
integer :: matches(size(words), 2)
integer :: i, j, k, l
! Initialize the matches array
matches = reshape((/ (0, 0) /), shape(matches))
! Iterate over the words
do i = 1, size(words)
! Iterate over the characters in the text
do j = 1, len_trim(text)
! Check if the current character is in the word
do k = 1, len_trim(words(i))
if (text(j:j) == words(i)(k:k)) then
! If it is, check if we have already found a match for this word
do l = 1, size(matches, 1)
if (matches(l, 1) == i) then
! If we have, update the end index of the match
matches(l, 2) = j
exit
end if
end do
! If we haven't, add a new match
if (l == size(matches, 1) + 1) then
matches(size(matches, 1) + 1, :) = [i, j]
end if
end if
end do
end do
end do
! Sort the matches by the first coordinate (word index) and then by the second coordinate (substring index)
call sort_matches(matches)
end function match_words_brute_force
subroutine sort_matches(matches)
! Sort the matches by the first coordinate (word index) and then by the second coordinate (substring index)
integer, intent(inout) :: matches(:, :)
integer :: i, j, temp
! Sort the matches by the first coordinate (word index)
do i = 1, size(matches, 1) - 1
do j = i + 1, size(matches, 1)
if (matches(i, 1) > matches(j, 1)) then
temp = matches(i, 1)
matches(i, 1) = matches(j, 1)
matches(j, 1) = temp
temp = matches(i, 2)
matches(i, 2) = matches(j, 2)
matches(j, 2) = temp
end if
end do
end do
! Sort the matches by the second coordinate (substring index)
do i = 1, size(matches, 1) - 1
do j = i + 1, size(matches, 1)
if (matches(i, 2) > matches(j, 2)) then
temp = matches(i, 2)
matches(i, 2) = matches(j, 2)
matches(j, 2) = temp
end if
end do
end do
end subroutine sort_matches
end module match_words
program main
use match_words, only : match_words_brute_force
implicit none
character(len=100) :: text
character(len=50) :: words(3)
integer :: matches(size(words), 2)
! Test case 1
text = "thestoryofleetcodeandme "
words = ["story ", "fleet ", "leetcode "]
matches = match_words_brute_force(text, words)
write (*, "(A, 3(I0, A, I0))") "Test case 1: ", matches
! Test case 2
text = "ababa "
words = ["aba ", "ab "]
matches = match_words_brute_force(text, words)
write (*, "(A, 4(I0, A, I0))") "Test case 2: ", matches
end program main
temp.f95:102:28:
102 | words = ["story ", "fleet ", "leetcode "]
| 1
Error: Different CHARACTER lengths (6/9) in array constructor at (1)
temp.f95:108:16:
108 | words = ["aba ", "ab "]
| 1
Error: Different CHARACTER lengths (4/3) in array constructor at (1)
def has_all_codes_in_range(s: str, n: int) -> bool:
substrings = set()
length = len(bin(n)) - 2
for i in range(len(s) - length + 1):
substrings.add(s[i:i + length])
return len(substrings) == n
1. Initialize an empty set called `substrings` to store unique binary substrings of length equal to the binary representation of `n`.
n and store it in length.s, starting from index 0 to len(s) - length:
a. Extract the substring of s with length length starting at index i.
b. Add the extracted substring to the substrings set.substrings is equal to n. If it is, then all integers in the range [1, n] had their binary representation in s.n, and false otherwise).bool hasAllCodesInRange(const std::string& s, int n) {
std::unordered_set<std::string> substrings;
int length = std::to_string(n).length();
for (int i = 0; i < s.length() - length + 1; ++i) {
substrings.insert(s.substr(i, length));
}
return substrings.size() == n;
}
1. Initialize an empty set called `substrings` to store unique binary substrings of length equal to the binary representation of `n`.
n and store it in length.s, starting from index 0 to len(s) - length:
a. Extract the substring of s with length length starting at index i.
b. Add the extracted substring to the substrings set.substrings is equal to n. If it is, then all integers in the range [1, n] had their binary representation in s.n, and false otherwise).