Valid Word Abbreviation

🏠 ⬅️ ➡️

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.

For example, a string such as "substitution " could be abbreviated as (but not limited to):

  • "s10n " ( "s ubstitutio n ")
  • "sub4u4 " ( "sub stit u tion ")
  • "12 " ( "substitution ")
  • "su3i1u2on " ( "su bst i t u ti on ")
  • "substitution " (no substrings replaced)

The following are not valid abbreviations:

  • "s55n " ( "s ubsti tutio n ", the replaced substrings are adjacent)
  • "s010n " (has leading zeros)
  • "s0ubstitution " (replaces an empty substring)

Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: word = "internationalization ", abbr = "i12iz4n " Output: true Explanation: The word "internationalization " can be abbreviated as "i12iz4n " ( "i nternational iz atio n ").

Example 2:

Input: word = "apple ", abbr = "a2e " Output: false Explanation: The word "apple " cannot be abbreviated as "a2e ".

Constraints:

  • 1 <= word.length <= 20
  • word consists of only lowercase English letters.
  • 1 <= abbr.length <= 10
  • abbr consists of lowercase English letters and digits.
  • All the integers in abbr will fit in a 32-bit integer.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=*), parameter :: word = "substitution "
    character(len=*), parameter :: abbr = "s10n "
    logical :: matches

    write(*,*) 'word: ', trim(word)
    write(*,*) 'abbr: ', trim(abbr)
    write(*,*) 'matches: ', matches(word, abbr)

contains

    function matches(str, abbr) result(res)
        implicit none
        character(len=*), intent(in) :: str, abbr
        logical :: res
        integer :: i, j, k, l

        res = .false.
        i = 1
        do while (i <= len_trim(str))
            j = index(str(i:), ' ')
            if (j == 0) then
                exit
            end if
            k = index(abbr, ' ')
            if (k /= 0) then
                ! there is a space in the abbreviation
                if (j > k) then
                    ! the substring before the space in the abbreviation is longer than the actual substring
                    exit
                else
                    ! the substring before the space in the abbreviation is shorter or equal to the actual substring
                    i = i + j - 1
                    cycle
                end if
            else
                ! no space in the abbreviation
                if (j > len_trim(abbr)) then
                    ! the actual substring is longer than the abbreviation
                    exit
                else
                    ! the actual substring is shorter or equal to the abbreviation
                    i = i + j - 1
                    cycle
                end if
            end if
            l = len_trim(str(i:i+j-1))
            if (l > 0) then
                ! the actual substring is not empty
                if (index(abbr, l) == 0) then
                    ! the length of the actual substring is not found in the abbreviation
                    exit
                else
                    ! the length of the actual substring is found in the abbreviation
                    i = i + j
                    cycle
                end if
            else
                ! the actual substring is empty
                exit
            end if
        end do
        if (i == len_trim(str)+1) then
            ! we reached the end of the string without finding a mismatch
            res = .true.
        end if
    end function matches

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

      integer :: i, j, k, l
      character(len=20) :: word, abbr
      logical :: match

      ! test case 1
      word = "internationalization "
      abbr = "i12iz4n "
      match = match_abbr(word, abbr)
      if (match) then
        print *, "Test case 1: PASS"
      else
        print *, "Test case 1: FAIL"
      end if

      ! test case 2
      word = "apple "
      abbr = "a2e "
      match = match_abbr(word, abbr)
      if (.not. match) then
        print *, "Test case 2: PASS"
      else
        print *, "Test case 2: FAIL"
      end if

      ! test case 3
      word = "substitution "
      abbr = "s10n "
      match = match_abbr(word, abbr)
      if (match) then
        print *, "Test case 3: PASS"
      else
        print *, "Test case 3: FAIL"
      end if

      ! test case 4
      word = "substitution "
      abbr = "sub4u4 "
      match = match_abbr(word, abbr)
      if (match) then
        print *, "Test case 4: PASS"
      else
        print *, "Test case 4: FAIL"
      end if

      ! test case 5
      word = "substitution "
      abbr = "12 "
      match = match_abbr(word, abbr)
      if (match) then
        print *, "Test case 5: PASS"
      else
        print *, "Test case 5: FAIL"
      end if

      ! test case 6
      word = "substitution "
      abbr = "su3i1u2on "
      match = match_abbr(word, abbr)
      if (match) then
        print *, "Test case 6: PASS"
      else
        print *, "Test case 6: FAIL"
      end if

      ! test case 7
      word = "substitution "
      abbr = "substitution "
      match = match_abbr(word, abbr)
      if (match) then
        print *, "Test case 7: PASS"
      else
        print *, "Test case 7: FAIL"
      end if

      ! test case 8
      word = "substitution "
      abbr = "s55n "
      match = match_abbr(word, abbr)
      if (match) then
        print *, "Test case 8: PASS"
      else
        print *, "Test case 8: FAIL"
      end if

      ! test case 9
      word = "substitution "
      abbr = "s010n "
      match = match_abbr(word, abbr)
      if (match) then
        print *, "Test case 9: PASS"
      else
        print *, "Test case 9: FAIL"
      end if

      ! test case 10
      word = "substitution "
      abbr = "s0ubstitution "
      match = match_abbr(word, abbr)
      if (match) then
        print *, "Test case 10: PASS"
      else
        print *, "Test case 10: FAIL"
      end if

      contains

      function match_abbr(word, abbr) result(match)
      implicit none
      character(len=*), intent(in) :: word, abbr
      logical :: match
      integer :: i, j, k, l

      match = .false.
      i = 1
      j = 1
      k = 1
      l = 1
      do while (i <= len(word) .and. j <= len(abbr))
        if (abbr(j:j) == '0') then
          j = j + 1
          cycle
        end if
        if (
🌐 Data from online sources 
def validWordAbbreviation(word, abbr):
    i, j = 0, 0
    while i < len(word) and j < len(abbr):
        if abbr[j].isdigit():
            if abbr[j] == '0': return False  # leading zero
            num = 0
            while j < len(abbr) and abbr[j].isdigit():
                num = num * 10 + int(abbr[j])
                j += 1
            i += num
        else:
            if word[i] != abbr[j]: return False
            i, j = i + 1, j + 1
    return i == len(word) and j == len(abbr)

The algorithm uses two pointers, i and j, to compare the characters in the word and the abbr. If the current character in abbr is a digit, we check if it's a leading zero and return false if so. Then, we sum all the consecutive digits to calculate the number and update i accordingly. If the current character is a letter, we compare the characters in word and abbr and return false if they're not equal. Finally, we check if we've reached the end of both the word and the abbr and return true if so.

🌐 Data from online sources 
bool validWordAbbreviation(string word, string abbr) {
    int i = 0, j = 0;
    while (i < word.size() && j < abbr.size()) {
        if (isdigit(abbr[j])) {
            if (abbr[j] == '0') return false; // leading zero
            int num = 0;
            while (j < abbr.size() && isdigit(abbr[j]))
                num = num * 10 + (abbr[j++] - '0');
            i += num;
        } else {
            if (word[i++] != abbr[j++]) return false;
        }
    }
    return i == word.size() && j == abbr.size();
}

The algorithm uses two pointers, i and j, to compare the characters in the word and the abbr. If the current character in abbr is a digit, we check if it's a leading zero and return false if so. Then, we sum all the consecutive digits to calculate the number and update i accordingly. If the current character is a letter, we compare the characters in word and abbr and return false if they're not equal. Finally, we check if we've reached the end of both the word and the abbr and return true if so.