Suggest a solution for this leetcode problem
One solution to this problem is to use two stacks. Here's a step by step guide:

- Initialize two stacks, one to store the indices of left parentheses '(' and the other to store the indices of '*' characters.
- Iterate over the characters in the string.
- If a character is '(', push its index to the left parentheses stack.
- If the character is '*', push its index to the '*' stack.
- If the character is ')', pop from the left parentheses stack if it's not empty, otherwise pop from the '*' stack. If both stacks are empty, then return False as there is no matching left parenthesis or '*' to balance this right parenthesis.
- After the iteration, we are left with indices of some '(''s and '*'s in their respective stacks. The '*'s can be used to balance the '('s from their right. So, for every remaining '(' in the stack, we need to ensure there is a '*' to its right. We can do this by checking that indices of '*'s are greater than indices of '(''s while popping from both stacks. If any '(' is left without a '*' to it's right, return False.
- Return True

Here is a sample code in Python:

```python
def checkValidString(s):
    left_parentheses = [] # stack to store indices of '('
    asterisk = [] # stack to store indices of '*'
    
    for i, char in enumerate(s):
        if char == '(':
            left_parentheses.append(i)
        elif char == '*':
            asterisk.append(i)
        else: # char == ')'
            if len(left_parentheses) > 0:
                left_parentheses.pop()
            elif len(asterisk) > 0:
                asterisk.pop()
            else:
                return False
    
    while len(left_parentheses) > 0 and len(asterisk) > 0:
        if left_parentheses.pop() > asterisk.pop():
            return False
    
    return len(left_parentheses) == 0
```

This solution has a time complexity of O(n) and space complexity of O(n), where n is the length of the input string.
Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.

An empty string is also valid.
Below is an instruction that describes a task, paired with an input that provides further context. Write a response that appropriately completes the request.

### Instruction:
Suggest a solution for this leetcode problem

### Input:
Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.

An empty string is also valid.

### Response:
One solution to this problem is to use two stacks. Here's a step by step guide:

- Initialize two stacks, one to store the indices of left parentheses '(' and the other to store the indices of '*' characters.
- Iterate over the characters in the string.
- If a character is '(', push its index to the left parentheses stack.
- If the character is '*', push its index to the '*' stack.
- If the character is ')', pop from the left parentheses stack if it's not empty, otherwise pop from the '*' stack. If both stacks are empty, then return False as there is no matching left parenthesis or '*' to balance this right parenthesis.
- After the iteration, we are left with indices of some '(''s and '*'s in their respective stacks. The '*'s can be used to balance the '('s from their right. So, for every remaining '(' in the stack, we need to ensure there is a '*' to its right. We can do this by checking that indices of '*'s are greater than indices of '(''s while popping from both stacks. If any '(' is left without a '*' to it's right, return False.
- Return True

Here is a sample code in Python:

```python
def checkValidString(s):
    left_parentheses = [] # stack to store indices of '('
    asterisk = [] # stack to store indices of '*'
    
    for i, char in enumerate(s):
        if char == '(':
            left_parentheses.append(i)
        elif char == '*':
            asterisk.append(i)
        else: # char == ')'
            if len(left_parentheses) > 0:
                left_parentheses.pop()
            elif len(asterisk) > 0:
                asterisk.pop()
            else:
                return False
    
    while len(left_parentheses) > 0 and len(asterisk) > 0:
        if left_parentheses.pop() > asterisk.pop():
            return False
    
    return len(left_parentheses) == 0
```

This solution has a time complexity of O(n) and space complexity of O(n), where n is the length of the input string.