language agnostic - How to find string path in a matrix of characters? -

how go implementing function check whether there path string in matrix of characters? moves left, right, , down in matrix, , cell movement.

the path can start entry in matrix. if cell occupied character of string on path, cannot occupied character again.

how go solving problem (psuedocode if prefer)? initial thinking interpret graph problem, matrix location vertex in graph.

edit: adding slow half-java half-pseudo-code version

class pair {     public pair(int x, int y) { this.x = x; this.y = y; }     public int x;     public int y; };  class main {     static vector<pair> singleton(pair p) {         vector<pair> v = new vector<pair>();         v.insert(p);         return v;     }      static void f(string str, int [][]matrix, int width, int height) {         vector<vector<pair>> v = new vector<vector<pair>>();         (int = 0; < height; ++i)             (int j = 0; j < width; ++j)                 try(i, j, str, matrix, width, height, v);     }      static void try(int i, int j, string str, int [][]matrix, int width, int height, vector<vector<pair>> v) {         int old_v_size = v.length;         if (i < 0 || >= height || j < 0 || j >= width) return;         if (str.length == 1) v.insert(singleton(new pair(i,j));         try(i+1,j,str.substr(1),matrix,width,height,v);         try(i-1,j,str.substr(1),matrix,width,height,v);         try(i,j+1,str.substr(1),matrix,width,height,v);         try(i,j-1,str.substr(1),matrix,width,height,v);         (int k = old_v_size; k < v.length; ++k) v[k].insert(new pair(i,j));     }  } 

old code follows below:

here solution in haskell (i replacing matrix here function gets 2 integers , returns value in matrix). function f accepts string, matrix function, width, height, , returns list of lists of tuples each possible solution.

f str matrix width height =     concat [try j str matrix width height | <- [0..width-1], j <- [0..height-1] ]     try j (c:cs) matrix width height | < 0 ||                                       >= height ||                                       j < 0 ||                                       j >= width ||                                       matrix j /= c = [] try j [c] matrix width height = [(i,j)] try j (c:cs) matrix width height =     concat  [map ((i,j):) $ try (i+1) j cs matrix width height,              map ((i,j):) $ try (i-1) j cs matrix width height,              map (c:) $ try (j+1) cs matrix width height,              map (c:) $ try (j-1) cs matrix width height] 

if want language please specify , send solution