I have a string S consisting of N letters 'a' or 'b'. This should return true when all occurrences of 'a' are before all occurrences of 'b' and return false otherwise.
b does not need to occur in S and a does not need to occur in S
For example
S='aabbb' returns true
S = 'ba' returns false
S = 'aaa' returns true
S= 'b' returns true
S='abba' returns false
this is my solution but it displays 1 extra true. I don't know why.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector <string> vec;
int n;
string item;
int contora=0,contorb=0;
cout<<"n: ";
cin>>n;
cout << "Enter a string: ";
for(int i=0;i<= n;i ){
getline(cin, item);
//cin>>item;
vec.push_back(item);
}
for (int j=0; j <= n; j ) {
cout << vec[j];
}
cout<<endl;
for (auto of:vec) {
if (of.find("ba") != std::string::npos)
cout << "false";
else
cout<<"true";
}
return 0;
}
CodePudding user response:
Wording it differently, you're trying to check if there are any characters in the string that come after a
. If the answer is no, your function will return true
, and false
otherwise.
bool HasCorrectOrder(char prefix_char, char suffix_char, std::string_view str) {
if (str.empty()) {
return true;
}
// Run through all the preceeding characters.
int index = 0;
while (str[index] == prefix_char && index < str.size()) {
index;
}
// At this point, if we've reached the end of the string, that means there are
// no characters after the preceeding character. So we can return true.
if (index == str.size()) {
return true;
}
// As there are more characters left, they should all be equal to the
// suffix_char in order for the ordering to be correct.
while (str[index] == suffix_char && index < str.size()) {
index;
}
return (index == str.size());
}
Running a quick check:
void RunTest() {
std::vector<std::string> test_strings = {"aabbb", "ba", "aaa", "b", "abba"};
for (std::string_view str : test_strings) {
std::cout << "S = " << str << " returns "
<< (HasCorrectOrder(/*prefix_char=*/'a',
/*suffix_char=*/'b', str) ? "true" : "false")
<< std::endl;
}
}
returns:
S = aabbb returns true
S = ba returns false
S = aaa returns true
S = b returns true
S = abba returns false
CodePudding user response:
Adding some debug output to the code shows a couple of issues:
- The first
for
loop reads inn 1
strings, while we are expecting the user to enter onlyn
strings. The secondfor
loop also printsn 1
strings, although that's not a problem, because the vector containsn 1
elements. - Due to mixing both
std::cin >>
andstd::getline
for reading user input, the first string read withstd::getline
is empty. You would need whether to:- use
std::getline
for all the user input readings (and, forn
, convert the string to a number), or - flush the input buffer with
cin.ignore
after thestd::cin >>
, as explained in this answer.
- use
The code below fixes those two issues and adds some debug output (it also follows a few best practices such as, not using namespace std;
, defining variables next to their first use, value-initializing local variables, and using block braces even for one-line blocks).
#include <iostream> // cin, cout
#include <limits>
#include <string> // getline
#include <vector>
int main() {
int n{};
std::cout << "n: ";
std::cin >> n;
std::cout << n << "\n\n";
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
std::vector<std::string> vec{};
for (int i = 0; i < n; i ) {
std::cout << "Enter a string: ";
std::string item{};
std::getline(std::cin, item);
std::cout << "item: " << i << ": '" << item << "'\n";
vec.push_back(item);
}
std::cout << "\n";
for (auto& of : vec) {
std::cout << "'" << of << "': ";
if (of.find("ba") != std::string::npos) {
std::cout << "false\n";
} else {
std::cout << "true\n";
}
}
}
// Outputs:
//
// n: 5
//
// Enter a string: item: 0: 'aabbb'
// Enter a string: item: 1: 'ba'
// Enter a string: item: 2: 'aaa'
// Enter a string: item: 3: 'b'
// Enter a string: item: 4: 'abba'
//
// 'aabbb': true
// 'ba': false
// 'aaa': true
// 'b': true
// 'abba': false
For this particular case, you could also use std::is_partitioned
. This algorithm tells you if all the elements of a range that satisfy a given predicate appear before all the elements that don't (see here). The predicate would check if a character is equal to 'a'
.
#include <algorithm> // is_partitioned
#include <cstring> // strlen
#include <fmt/core.h>
int main() {
for (auto&& s : { "aabbb", "ba", "aaa", "b", "abba" }) {
fmt::print("'{}': {}\n", s, std::is_partitioned(s, s strlen(s),
[](unsigned char c) { return c == 'a'; }));
}
}
CodePudding user response:
After fixing the loop logic, here is another simple solution you could use, with the is_sorted algorithm:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
int main() {
// ...
for (auto of : vec)
std::cout << std::boolalpha << std::ranges::is_sorted(of);
}
This compiles with C 20 support, and it works because strings are ranges of characters, for which an operator<
is defined. It happens to be the case that 'a' < 'b', so this simple expression is all you need.