Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at consecutive positions would differ by exactly one character. Example For inputArray = ["aba", "bbb", "bab"], the output should be stringsRearrangement(inputArray) = false; All rearrangements don't satisfy the description condition. For inputArray = ["ab", "bb", "aa"], the output should be stringsRearrangement(inputArray) = true. Strings can be rearranged in the following way: "aa", "ab", "bb" |
code>>
bool stringsRearrangement(std::vector<std::string> inputArray)
{
return stringsRearrangement(inputArray, 0, inputArray.size());
}
void swap(std::vector<std::string>& v, int value, int value2)
{
auto temp = v[value];
v[value] = v[value2];
v[value2] = temp;
}
bool stringsRearrangement(std::vector<std::string> inputArray, int t, int dept)
{
bool check = false;
if (dept == t)
{
int c = 0;
for (int i = 0; i<inputArray.size() - 1; i++)
{
c = 0;
for (int j = 0; j < inputArray[i].size(); j++)
{
if (inputArray[i][j] != inputArray[i + 1][j])
c++;
}
if (c != 1) break;
}
return (c == 1);
}
else
{
for (int i = t; i < dept; i++)
{
swap(inputArray, t, i);
check = stringsRearrangement(inputArray, t + 1, dept);
swap(inputArray, i, t);
if (check) return true;
}
}
return check;
}
'알고리즘 > codefights' 카테고리의 다른 글
| 35>firstDigit (0) | 2017.07.31 |
|---|---|
| 34>extractEachKth (0) | 2017.07.31 |
| 32>absoluteValuesSumMinimization (0) | 2017.07.08 |
| 31>depositProfit (0) | 2017.07.06 |
| 30>circleOfNumbers (0) | 2017.07.06 |