Optimizing a recursive path finding algorithm

Question

On input i get width and height of matrix, string of text and another string of finalText I want to reach. The characters of the first string are assigned to matrix. My goal is to find shortest way to create finalText from characters in matrix, starting at position (0,0), and return number of steps.

So I create a dictionary of all coordinates and characters from finalText.

Dictionary<Tuple<int, int>, char> coords = new Dictionary<Tuple<int, int>, char>();
for (int i = 0; i < height; i++)
{
  for (int j = 0; j < width; j++){
   if (finalText.Contains(matrix[j, i]))
    coords.Add(new Tuple<int, int>(j, i), matrix[j, i]);
  }
}

And then use it in my function. I basically calculate steps in all possible paths and then return the shortest one.

static int ShortestPath(char[,] matrix, string str, int x, int y, int steps, Dictionary<Tuple<int,int>,char> coords)
{
    if (str.Length == 0)
    {
        return steps;
    }

    else
    {
        List<int> l = new List<int>();

        foreach (var item in coords)
        {
            if (item.Value == str[0])
                l.Add(ShortestPath(matrix, str.Substring(1), item.Key.Item1, item.Key.Item2,
                    steps + (Math.Abs(x - item.Key.Item1) + Math.Abs(y - item.Key.Item2)), coords));
        }
                
        int min = l[0];
        for (int i = 1; i < l.Count; i++)
        {
            if (l[i] < min)
                min = l[i];
        }
        return min;
    }
}

The algorithm is working, but for bigger matrices it's too slow and I have no idea how to optimize it or do it otherwise.