C++ MyProgrammingLab problem Implement the isSimilarBag() function below // retu
ID: 3562479 • Letter: C
Question
C++ MyProgrammingLab problem
Implement the isSimilarBag() function below
// return true iff s and t are the same length and the bag of letters in s is "similar" to the bag of letters in t
// Specifically, let diff(ch, s, t) be the absolute difference of the number of occurrences of ch in s and t.
// Then we want diff('a',s,t) + diff('b',s,t) + ... + diff('z',s,t) <= L/3, where L is the common length of s and t.
// precondition: s and t contain only lowercase letters {'a'... 'z'}
bool isSimilarBag(const string &s, const string &t) ;
Do not create any other functions or write the entire program.
Explanation / Answer
//Implement the isSimilarBag() function below
// return true iff s and t are the same length and the bag of letters in s is "similar" to the bag of letters in t
// Specifically, let diff(ch, s, t) be the absolute difference of the number of occurrences of ch in s and t.
// Then we want diff('a',s,t) + diff('b',s,t) + ... + diff('z',s,t) <= L/3, where L is the common length of s and t.
// precondition: s and t contain only lowercase letters {'a'... 'z'}
bool isSimilarBag(const string &s, const string &t)
{
int s_diff[26] ={0};
int t_diff[26] ={0};
if(s.length() != t.length()) return false;
for(int i=0; i<s.length(); i++)
s_diff[s[i]-'a']++;
for(int i=0; i<s.length(); i++)
t_diff[s[i]-'a']++;
int sum = 0;
for(int k=0; k<26; k++)
{
sum = sum + (s_diff[k]>t_diff[k]?(s_diff[k]-t_diff[k]):(t_diff[k]-s_diff[k]));
}
return 3*sum<=s.length();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.