-
Notifications
You must be signed in to change notification settings - Fork 4
/
stringsRearrangement.cpp
70 lines (56 loc) · 2.21 KB
/
stringsRearrangement.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// Given an array of equal-length strings, you'd like to know if it's possible to rearrange the order of the elements in such a way that each consecutive pair of strings
// differ by exactly one character. Return true if it's possible, and false if not.
// Note: You're only rearranging the order of the strings, not the order of the letters within the strings!
// Example
// For inputArray = ["aba", "bbb", "bab"], the output should be
// stringsRearrangement(inputArray) = false.
// There are 6 possible arrangements for these strings:
// ["aba", "bbb", "bab"]
// ["aba", "bab", "bbb"]
// ["bbb", "aba", "bab"]
// ["bbb", "bab", "aba"]
// ["bab", "bbb", "aba"]
// ["bab", "aba", "bbb"]
// None of these satisfy the condition of consecutive strings differing by 1 character, so the answer is false.
// For inputArray = ["ab", "bb", "aa"], the output should be
// stringsRearrangement(inputArray) = true.
// It's possible to arrange these strings in a way that each consecutive pair of strings differ by 1 character (eg: "aa", "ab", "bb" or "bb", "ab", "aa"), so return true.
bool testStrings(string myString, string mySubString)
{
if(myString.length() != mySubString.length())
return true;
else if(myString == mySubString)
return true;
bool test = false;
for(int i = 0; i < myString.size(); i++)
if(myString[i] != mySubString[i])
if(test == false)
test = true;
else
return true;
return false;
}
bool testArray(std::vector<std::string> inputArray)
{
for(int i = 1; i < inputArray.size(); i++)
if(testStrings(inputArray[i], inputArray[i-1]))
return false;
return true;
}
bool test = false;
void permute(std::vector<std::string> inputArray, int start = 0)
{
if (start == inputArray.size() && testArray(inputArray))
test = true;
else
for (int i = start; i < inputArray.size(); i++)
{
swap(inputArray[i], inputArray[start]);
permute(inputArray, start + 1);
swap(inputArray[i], inputArray[start]);
}
}
bool stringsRearrangement(std::vector<std::string> inputArray) {
permute(inputArray);
return test;
}