Friday, April 17, 2015

Print permutations of a string

Problem: Print all permutations of a given string

Implementation:

void stringPerm(std::string s, int len, int i = 0)
{
if(i == len)
std::cout<<s<<'\n';
else
{
for(int j = i; j < len; ++j)
{
if(i != j && s[i] == s[j])
continue;
std::swap(s[i], s[j]);
stringPerm(s, len, i + 1);
std::swap(s[i], s[j]);
}
}
}

Complexity: O(n*n!)

2 comments:

  1. no need to calculate length each time,it is constant length... can u expalane little bit about back tracking... :)

    ReplyDelete
    Replies
    1. Yes, you are right, no need to calculate length each time, can be taken as parameter in the method. I will update the solution.
      Thank for mentioning it,

      Delete