We are assuming that $A$ and $B$ are both connected and contain their boundary points. (If we do not assume $A$ and $B$ are connected then the problem becomes much harder.) Let $(A_i)$ be the closures of the components of $S - A$. Let $(B_j)$ be closures of the components of $S - B$. Define $(g_i, b_i, s_i)$ to be the genus of $A_i$, the size $|\partial A_i|$, and the size $|A \cap A_i|$, respectively.
We now sort the list $(A_i)$ using the complexities $(g, b, s)$. We do the same for the list $(B_j)$. Finally, there is a homeomorphism of $S$ sending $A$ to $B$ if and only if the two lists of complexities are identical.
To produce an "explicit" homeomorphism is much more work. Any algorithm will be sensitive to the details of how the data (of $S$, $A$, and $B$) are presented. One technique is to carefully order the boundary components of $A$ and $B$, compute all pairwise intersection numbers, and then perform Dehn twists to reduce the intersection numbers to zero. This is morally similar to Lee Mosher's automatic structure for the mapping class group.