A sentence consists of lowercase letters ('a' to 'z'), digits ('0' to '9'), hyphens ('-'), punctuation marks ('!', '.', and ','), and spaces (' ') only. Each sentence can be broken down into one or more tokens separated by one or more spaces ' '.
A token is a valid word if all three of the following are true:
'-'. If present, it must be surrounded by lowercase characters ( "a-b " is valid, but "-ab " and "ab- " are not valid)."ab, ", "cd! ", and ". " are valid, but "a!b " and "c., " are not valid).Examples of valid words include "a-b. ", "afad ", "ba-c ", "a! ", and "! ".
Given a string sentence, return the number of valid words in sentence.
Example 1:
Input: sentence = "cat and dog " Output: 3 Explanation: The valid words in the sentence are "cat ", "and ", and "dog ".
Example 2:
Input: sentence = "!this 1-s b8d! " Output: 0 Explanation: There are no valid words in the sentence. "!this " is invalid because it starts with a punctuation mark. "1-s " and "b8d " are invalid because they contain digits.
Example 3:
Input: sentence = "alice and bob are playing stone-game10 " Output: 5 Explanation: The valid words in the sentence are "alice ", "and ", "bob ", "are ", and "playing ". "stone-game10 " is invalid because it contains digits.
Constraints:
1 <= sentence.length <= 1000sentence only contains lowercase English letters, digits, ' ', '-', '!', '.', and ','.1 token.program main
implicit none
character(len=:), allocatable :: sentence
integer :: num_valid_words
! Examples from the problem statement
allocate(character(len=4) :: sentence)
sentence = "cat and dog "
print *, count_valid_words(sentence)
deallocate(sentence)
allocate(character(len=7) :: sentence)
sentence = "!this 1-s b8d! "
print *, count_valid_words(sentence)
deallocate(sentence)
allocate(character(len=16) :: sentence)
sentence = "alice and bob are playing stone-game10 "
print *, count_valid_words(sentence)
deallocate(sentence)
contains
function count_valid_words(sentence) result(num_valid_words)
implicit none
character(len=*), intent(in) :: sentence
integer :: i, j, k, num_valid_words
num_valid_words = 0
do i = 1, len_trim(sentence)
if (is_valid_word(sentence(i:))) then
num_valid_words = num_valid_words + 1
end if
end do
contains
logical function is_valid_word(word)
implicit none
character(len=*), intent(in) :: word
integer :: i, j
is_valid_word = .false.
! Check if word contains only lowercase letters, hyphens, and/or punctuation
do i = 1, len_trim(word)
if (ichar(word(i:i)) < ichar('a') .or. &
ichar(word(i:i)) > ichar('z') .and. &
ichar(word(i:i)) < ichar('0') .or. &
ichar(word(i:i)) > ichar('9') .and. &
ichar(word(i:i)) /= ichar('-') .and. &
ichar(word(i:i)) /= ichar('.') .and. &
ichar(word(i:i)) /= ichar(',') .and. &
ichar(word(i:i)) /= ichar('!')) then
return
end if
end do
! Check if there is at most one hyphen
i = index(word, '-')
if (i == 0) then
is_valid_word = .true.
else if (i == 1) then
is_valid_word = .true.
else if (i == len_trim(word)) then
is_valid_word = .true.
else
return
end if
! Check if there is at most one punctuation mark
i = index(word, '.')
j = index(word, ',')
k = index(word, '!')
if (i == 0 .and. j == 0 .and. k == 0) then
is_valid_word = .true.
else if (i == len_trim(word) .and. j == 0 .and. k == 0) then
is_valid_word = .true.
else if (j == len_trim(word) .and. i == 0 .and. k == 0) then
is_valid_word = .true.
else if (k == len_trim(word) .and. i == 0 .and. j == 0) then
is_valid_word = .true.
else
return
end if
end function is_valid_word
end function count_valid_words
end program maintemp.f95:37:12:
37 | contains
| 1
Error: CONTAINS statement at (1) is already in a contained program unit
temp.f95:39:25:
39 | logical function is_valid_word(word)
| 1
Error: Syntax error in data declaration at (1)
temp.f95:40:25:
40 | implicit none
| 1
Error: Duplicate IMPLICIT NONE statement at (1)
temp.f95:41:48:
41 | character(len=*), intent(in) :: word
| 1
Error: Unexpected data declaration statement at (1)
temp.f95:42:24:
42 | integer :: i, j
| 1
Error: Symbol ‘i’ at (1) already has basic type of INTEGER
temp.f95:44:26:
44 | is_valid_word = .false.
| 1
Error: ‘is_valid_word’ at (1) is not a variable
temp.f95:48:33:
48 | if (ichar(word(i:i)) < ichar('a') .or. &
| 1
Error: Syntax error in argument list at (1)
temp.f95:57:19:
57 | end if
| 1
Error: Expecting END DO statement at (1)
temp.f95:63:30:
63 | is_valid_word = .true.
| 1
Error: ‘is_valid_word’ at (1) is not a variable
temp.f95:65:30:
65 | is_valid_word = .true.
| 1
Error: ‘is_valid_word’ at (1) is not a variable
temp.f95:67:30:
67 | is_valid_word = .true.
| 1
Error: ‘is_valid_word’ at (1) is not a variable
temp.f95:77:30:
77 | is_valid_word = .true.
| 1
Error: ‘is_valid_word’ at (1) is not a variable
temp.f95:79:30:
79 | is_valid_word = .true.
| 1
Error: ‘is_valid_word’ at (1) is not a variable
temp.f95:81:30:
81 | is_valid_word = .true.
| 1
Error: ‘is_valid_word’ at (1) is not a variable
temp.f95:83:30:
83 | is_valid_word = .true.
| 1
Error: ‘is_valid_word’ at (1) is not a variable
temp.f95:88:34:
88 | end function is_valid_word
| 1
Error: Expected label ‘count_valid_words’ for END FUNCTION statement at (1)
temp.f95:47:35:
47 | do i = 1, len_trim(word)
| 1
Error: Symbol ‘word’ at (1) has no IMPLICIT type
temp.f95:32:16:
32 | if (is_valid_word(sentence(i:))) then
| 1
Error: Function ‘is_valid_word’ at (1) has no IMPLICIT type; did you mean ‘count_valid_words’?
module tokenize
implicit none
contains
function tokenize_sentence(sentence) result(tokens)
character(len=*), intent(in) :: sentence
type(token_type) :: tokens(size(sentence))
integer :: i, j, k
! Initialize the tokens array
tokens = token_type(size(sentence))
! Loop through the characters in the sentence
do i = 1, size(sentence)
! If the current character is a space, move on to the next token
if (sentence(i:i) == ' ') then
cycle
end if
! If the current character is a hyphen, check if it is surrounded by lowercase characters
if (sentence(i:i) == '-') then
if (i == 1 .or. i == size(sentence)) then
! If the hyphen is at the beginning or end of the sentence, it is invalid
tokens(i)%valid = .false.
cycle
end if
! Check if the character before the hyphen is lowercase
if (sentence(i-1:i-1) /= 'a' .and. sentence(i-1:i-1) /= 'b' .and. &
sentence(i-1:i-1) /= 'c' .and. sentence(i-1:i-1) /= 'd' .and. &
sentence(i-1:i-1) /= 'e' .and. sentence(i-1:i-1) /= 'f' .and. &
sentence(i-1:i-1) /= 'g' .and. sentence(i-1:i-1) /= 'h' .and. &
sentence(i-1:i-1) /= 'i' .and. sentence(i-1:i-1) /= 'j' .and. &
sentence(i-1:i-1) /= 'k' .and. sentence(i-1:i-1) /= 'l' .and. &
sentence(i-1:i-1) /= 'm' .and. sentence(i-1:i-1) /= 'n' .and. &
sentence(i-1:i-1) /= 'o' .and. sentence(i-1:i-1) /= 'p' .and. &
sentence(i-1:i-1) /= 'q' .and. sentence(i-1:i-1) /= 'r' .and. &
sentence(i-1:i-1) /= 's' .and. sentence(i-1:i-1) /= 't' .and. &
sentence(i-1:i-1) /= 'u' .and. sentence(i-1:i-1) /= 'v' .and. &
sentence(i-1:i-1) /= 'w' .and. sentence(i-1:i-1) /= 'x' .and. &
sentence(i-1:i-1) /= 'y' .and. sentence(i-1:i-1) /= 'z') then
! If the character before the hyphen is not lowercase, the hyphen is invalid
tokens(i)%valid = .false.
cycle
end if
! Check if the character after the hyphen is lowercase
if (sentence(i+1:i+1) /= 'a' .and. sentence(i+1:i+1) /= 'b' .and. &
sentence(i+1:i+1) /= 'c' .and. sentence(i+1:i+1) /= 'd' .and. &
sentence(i+1:i+1) /= 'e' .and. sentence(i+1:i+1) /= 'f' .and. &
sentence(i+1:i+1) /= 'g' .and. sentence(i+1:i+1) /= 'h' .and. &
sentence(i+1:i+1) /= 'i' .and. sentence(i+1:i+1) /= 'j' .and. &
sentence(i
temp.f95:10:17:
10 | type(token_type) :: tokens(size(sentence))
| 1
Error: Derived type ‘token_type’ at (1) is being used before it is defined
temp.f95:7:51:
7 | function tokenize_sentence(sentence) result(tokens)
| 1
Error: Function result ‘tokens’ at (1) has no IMPLICIT type
temp.f95:58:22:
58 | sentence(i
| 1
Error: Missing ‘)’ in statement at or before (1)
f951: Error: Unexpected end of file in ‘temp.f95’
def findPeakGrid(mat: List[List[int]]) -> List[int]:
m, n = len(mat), len(mat[0])
l, r = 0, n - 1
while l < r:
mid = (l + r) // 2
max_row = 0
for i in range(1, m):
if mat[i][mid] > mat[max_row][mid]:
max_row = i
if mat[max_row][mid] < mat[max_row][mid + 1]:
l = mid + 1
else:
r = mid
max_row = 0
for i in range(1, m):
if mat[i][l] > mat[max_row][l]:
max_row = i
return [max_row, l]
The algorithm is a modification of the binary search algorithm. We start by finding the middle column mid. For this column, we find the row max_row with the maximum element. Then, we compare the maximum element with its right neighbor.
If the right neighbor is greater, we know that there must be a peak element in the columns to the right, so we update l = mid + 1. Otherwise, we know that there must be a peak element in the columns to the left or at the current column, so we update r = mid.
Repeat this process until l == r. At this point, the maximum element in the column l is a peak element. We find the row max_row with the maximum element in the column l and return its position [max_row, l].
Since we are using binary search, the time complexity of the algorithm is O(m log(n)) or O(n log(m)).
#include <vector>
using namespace std;
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) / 2;
int max_row = 0;
for (int i = 1; i < m; i++) {
if (mat[i][mid] > mat[max_row][mid]) {
max_row = i;
}
}
if (mat[max_row][mid] < mat[max_row][mid + 1]) {
l = mid + 1;
} else {
r = mid;
}
}
int max_row = 0;
for (int i = 1; i < m; i++) {
if (mat[i][l] > mat[max_row][l]) {
max_row = i;
}
}
return {max_row, l};
}
The algorithm is a modification of the binary search algorithm. We start by finding the middle column mid. For this column, we find the row max_row with the maximum element. Then, we compare the maximum element with its right neighbor.
If the right neighbor is greater, we know that there must be a peak element in the columns to the right, so we update l = mid + 1. Otherwise, we know that there must be a peak element in the columns to the left or at the current column, so we update r = mid.
Repeat this process until l == r. At this point, the maximum element in the column l is a peak element. We find the row max_row with the maximum element in the column l and return its position [max_row, l].
Since we are using binary search, the time complexity of the algorithm is O(m log(n)) or O(n log(m)).