Is it possible better than this ?

help
,
1

There is a string whose characters can only be either ‘a’, ‘b’ or ‘’ (there can be only one ‘’ in the string). At each step, we can modify the string as follows:
1. ‘’ can be swapped with its adjacent character, example “a_ba” can be changed to either “aba” or “ab_a”.
2. Two characters adjacent to ‘’ (both on the same side of ‘’) can be reversed along with the ‘’ if both characters are different, example, “aa_ba” can be changed to “aaab” but not to “aaba” because both characters are ‘a’.
You are given two strings, the initial state and the final state (lengths will be same), you have to output the minimum number of steps required to change the string in initial state to the string in the final state.
example:
input: a_b ab
output: 1
input: abaa_a b_aaaa
output: 4
reason for example 2:- abaa_a -> aba_aa -> ab_aaa -> _baaaa -> b_aaaa

The best algorithm i come up with is , to generate all strings recursively by performing operations and when we get desired simply update the min operation.But this is too complex , cant it be done in better way ?

#include <iostream>
#include <string>
#include <deque>
#include <set>

// first: intermediate string; second: underscore position
typedef std::pair<std::string, int> StringPair;
// first: above; second: number of steps so far
typedef std::pair<StringPair, int> StatePair;
typedef std::deque<StatePair> Queue;
typedef std::set<std::string> StringSet;

int Swap(const std::string &input, const std::string &output)
{
	Queue Q;
	
	// Used to keep track of what states we have already explored
	StringSet S;
	
	// Position of the underscore
	int us_pos = input.find('_');

	StatePair p(StringPair(input, us_pos), 0);
	Q.push_back(p);

	unsigned strlength = input.length();

	while (!Q.empty()) {
		StatePair p = Q.front();
		Q.pop_front();

		const std::string state_string = p.first.first;
		us_pos = p.first.second;
		int len = p.second;

		// Finished?
		if (state_string == output)
			return len;

		// Have we already explored this state?
		if (S.count(state_string)) continue;

		S.insert(state_string);

		std::string next_state_string;

		// First branch
		if (us_pos > 0) {
			next_state_string = state_string;
			next_state_string[us_pos] = next_state_string[us_pos-1];
			next_state_string[us_pos-1] = '_';
			p = StatePair(StringPair(next_state_string, us_pos-1), len+1);
			Q.push_back(p);
		}

		// Second branch
		if (us_pos < strlength-1) {
			next_state_string = state_string;
			next_state_string[us_pos] = next_state_string[us_pos+1];
			next_state_string[us_pos+1] = '_';
			p = StatePair(StringPair(next_state_string, us_pos+1), len+1);
			Q.push_back(p);
		}

		// Third branch
		if (us_pos > 1) {
			next_state_string = state_string;
			char c1 = next_state_string[us_pos-2];
			char c2 = next_state_string[us_pos-1];
			if (c1 != c2) {
				next_state_string[us_pos] = c1;
				next_state_string[us_pos-2] = '_';
				p = StatePair(StringPair(next_state_string, us_pos-2), len+1);
				Q.push_back(p);
			}
		}

		// Fourth branch
		if (us_pos < strlength-2) {
			next_state_string = state_string;
			char c1 = next_state_string[us_pos+2];
			char c2 = next_state_string[us_pos+1];
			if (c1 != c2) {
				next_state_string[us_pos] = c1;
				next_state_string[us_pos+2] = '_';
				p = StatePair(StringPair(next_state_string, us_pos+2), len+1);
				Q.push_back(p);
			}
		}
	}

	return -1;
}
1 Like