Long Pressed Name

🏠 ⬅️ ➡️

Your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.

You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Example 1:

Input: name = "alex ", typed = "aaleex " Output: true Explanation: 'a' and 'e' in 'alex' were long pressed.

Example 2:

Input: name = "saeed ", typed = "ssaaedd " Output: false Explanation: 'e' must have been pressed twice, but it was not in the typed output.

Constraints:

  • 1 <= name.length, typed.length <= 1000
  • name and typed consist of only lowercase English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i
    character(len=1000) :: name, typed

    do i = 1, size(examples)
        read(examples(i), *) name, typed
        write(*,*) solve(name, typed)
    end do

contains

    function solve(name, typed) result(res)
        implicit none
        character(len=*), intent(in) :: name, typed
        logical :: res

        ! TODO: Implement me

    end function solve

    character(len=1000), parameter :: examples(3) = ["alex ", &
                                                     "saeed ", &
                                                     "leelee "]

end program main
✅ Compiled
✅ Executed
❌ Correct 
module long_pressed_name

implicit none

contains

function is_long_pressed_name(name, typed) result(is_valid)

! Declare the input and output variables
character(len=*), intent(in) :: name
character(len=*), intent(in) :: typed
logical :: is_valid

! Declare the local variables
integer :: i, j

! Initialize the output variable
is_valid = .false.

! Check if the length of the name and typed strings are the same
if (len(name) /= len(typed)) then
    return
endif

! Initialize the indices for the name and typed strings
i = 1
j = 1

! Loop through the characters of the name and typed strings
do while (i <= len(name) .and. j <= len(typed))
    ! Check if the characters match
    if (name(i:i) == typed(j:j)) then
        ! Increment the indices
        i = i + 1
        j = j + 1
    else
        ! Check if the typed character is the same as the previous character
        if (j > 1 .and. typed(j-1:j-1) == typed(j:j)) then
            ! Increment the index of the typed string
            j = j + 1
        else
            ! The characters do not match, return false
            return
        endif
    endif
enddo

! Check if all the characters of the name have been matched
if (i > len(name)) then
    is_valid = .true.
endif

end function is_long_pressed_name

end module long_pressed_name

! Test the function with the provided examples
program test_long_pressed_name

use long_pressed_name

implicit none

! Declare the variables
character(len=1000) :: name
character(len=1000) :: typed
logical :: is_valid

! Test case 1:
name = "alex "
typed = "aaleex "
is_valid = is_long_pressed_name(name, typed)
if (is_valid) then
    print *, "Test case 1: Pass"
else
    print *, "Test case 1: Fail"
endif

! Test case 2:
name = "saeed "
typed = "ssaaedd "
is_valid = is_long_pressed_name(name, typed)
if (.not. is_valid) then
    print *, "Test case 2: Pass"
else
    print *, "Test case 2: Fail"
endif

! Test case 3:
name = "leelee "
typed = "lleeelee "
is_valid = is_long_pressed_name(name, typed)
if (is_valid) then
    print *, "Test case 3: Pass"
else
    print *, "Test case 3: Fail"
endif

! Test case 4:
name = "laiden "
typed = "laiden "
is_valid = is_long_pressed_name(name, typed)
if (is_valid) then
    print *, "Test case 4: Pass"
else
    print *, "Test case 4: Fail"
endif

! Test case 5:
name = "laiden "
typed = "laiden "
is_valid = is_long_pressed_name(name, typed)
if (is_valid) then
    print *, "Test case 5: Pass"
else
    print *, "Test case 5: Fail"
endif

end program test_long_pressed_name
🌐 Data from online sources 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def constructFromPrePost(self, pre, post):
        def buildTree(preStart, preEnd, postStart, postEnd):
            if preStart == preEnd:
                return None

            root = TreeNode(pre[preStart])

            if preStart + 1 == preEnd:
                return root

            leftRoot = pre[preStart + 1]

            leftSize = 0
            for i in range(postStart, postEnd):
                if post[i] == leftRoot:
                    leftSize = i - postStart + 1
                    break

            root.left = buildTree(preStart + 1, preStart + 1 + leftSize, postStart, postStart + leftSize)
            root.right = buildTree(preStart + 1 + leftSize, preEnd, postStart + leftSize, postEnd - 1)

            return root

        return buildTree(0, len(pre), 0, len(post))

The reconstruction of binary tree can be done using a divide-and-conquer strategy.

  1. The first element of the preorder array is the root node.
  2. The second element of the preorder array is the root of the left subtree.
  3. Find the index of the left subtree root in the postorder array. The left subtree size can be calculated as index - postStart + 1.
  4. The left subtree ranges can be found using preStart + 1 and preStart + 1 + leftSize in the preorder array, postStart and postStart + leftSize in the postorder array.
  5. The right subtree ranges can be found with preStart + 1 + leftSize and preEnd in the preorder array, postStart + leftSize and postEnd - 1 in the postorder array.
  6. Recursively build the left subtree and right subtree with the calculated ranges.
  7. Connect the left subtree and right subtree to the current root node.

The overall time complexity is O(N^2) due to finding the index of the left subtree root. The space complexity is O(N) because of the recursion stack.

🌐 Data from online sources 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        return buildTree(preorder, 0, preorder.size(), postorder, 0, postorder.size());
    }

    TreeNode* buildTree(vector<int>& pre, int preStart, int preEnd, vector<int>& post, int postStart, int postEnd) {
        if (preStart == preEnd) return nullptr;

        TreeNode* root = new TreeNode(pre[preStart]);

        if (preStart + 1 == preEnd) return root;

        int leftRoot = pre[preStart + 1];

        int leftSize = 0;
        for (int i = postStart; i < postEnd; ++i) {
            if (post[i] == leftRoot) {
                leftSize = i - postStart + 1;
                break;
            }
        }

        root->left = buildTree(pre, preStart + 1, preStart + 1 + leftSize, post, postStart, postStart + leftSize);
        root->right = buildTree(pre, preStart + 1 + leftSize, preEnd, post, postStart + leftSize, postEnd - 1);

        return root;
    }
};

The reconstruction of binary tree can be done using a divide-and-conquer strategy.

  1. The first element of the preorder array is the root node.
  2. The second element of the preorder array is the root of the left subtree.
  3. Find the index of the left subtree root in the postorder array. The left subtree size can be calculated as index - postStart + 1.
  4. The left subtree ranges can be found using preStart + 1 and preStart + 1 + leftSize in the preorder array, postStart and postStart + leftSize in the postorder array.
  5. The right subtree ranges can be found with preStart + 1 + leftSize and preEnd in the preorder array, postStart + leftSize and postEnd - 1 in the postorder array.
  6. Recursively build the left subtree and right subtree with the calculated ranges.
  7. Connect the left subtree and right subtree to the current root node.

The overall time complexity is O(N^2) due to finding the index of the left subtree root. The space complexity is O(N) because of the recursion stack.