Given a r x c matrix and an input String of length n.
Check if the input string can fit in the matrix;
Rules

1. can occupy " ",
2. cannot occupy #
3. there should not be any leading or trailing spaces or other alphabets (# is ok).
4. Cannot update existing letters
5. You can place the string either horizontally (left to right) or vertically(top to bottom)
6. need to be stored contiguously in the same row/col
   e.g

3 x 3 [
 "#", " ", "#"
 " ", " ", "#"
 "#", "c", " "
 ]
 str ->abc
 ans -> true
 "ab" can be placed as follows and "c" already exists:
 [
 "#", "a", "#"
 " ", "b", "#"
 "#", "c", " "
 ]
 
 
 2 x 2[
 " ", " "
 " ", " "
 ]
 str -> a
 ans-> false ( no matter where you place "a", there will be a leading or trailing space in the row or column)

I could only come up with a brute force solution O(r * c * n) -> go throught all the points and check if the string can fit according to the given rules.
Not sure if it is going to be good enought as I later realized that I missed an edge case.
What would be a better approach?

Update: As pointed out by @vishalmittal1993 the time complexity of this approach is actually O(r * c)
Since there are only a limited number of valid start points we would never go through a point more than 4 times. (twice while row parsing, and twice while column parsing).