A better solution for comparing string patterns.?

Question

Task : Create a function that returns true if two strings share the same letter pattern, and false otherwise.

I found a way to solve this task but I think it could be more simple and short. I converted all same letters to a specific char character for 2 strings. Then end of the process checked whether they are same or not. Any ideas for simpler solutions ?

#include <iostream>
#include <string>

using namespace std;

bool LetterPattern(string str1, string str2) { 
    // Controlling whether they have same size or not
    if (str1.length() != str2.length()) {
        return false; 
    }
    else {
        // Checking for ABC XYZ format type 
        int counter = 0;
        for (int i = 0; i < str1.length()-1; i++) {
            for (int k = i+1; k < str1.length(); k++) {
                if (str1[i] == str1[k]) {
                    counter++;
                }
            }
        }
        int counter2 = 0;
        for (int i = 0; i < str2.length() - 1; i++) {
            for (int k = i + 1; k < str2.length(); k++) {
                if (str2[i] == str2[k]) {
                    counter2++;
                }
            }
        }
        
        if (counter == 0 && counter2 == 0) {
            return true;
        }
        // I added the above part because program below couldn't return 1 for completely different letter formats
        // like XYZ ABC DEF etc.
        
        //Converting same letters to same chars for str1
        for (int i = 0; i < str1.length()-1; i++) {
            for (int k = i+1; k < str1.length(); k++) { 
                if (str1[i] == str1[k]) {
                    str1[k] = (char)i;
                }
            }
            str1[i] = (char)i;
        }
    }
    //Converting same letters to same chars for str1
    for (int i = 0; i < str2.length() - 1; i++) {
        for (int k = i + 1; k < str2.length(); k++) { 
            if (str2[i] == str2[k]) {
                str2[k] = (char)i;
            }
        }
        str2[i] = (char)i;
    }
    if (str1 == str2) { // After converting strings, it checks whether they are same or not
        return true;
    }
    else {
        return false;
    }
}
    

int main(){
    cout << "Please enter two string variable: ";
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Same Letter Pattern: " << LetterPattern(str1, str2);

    system("pause>0");
}

Examples:

str1	str2	result
AABB	CCDD	true
ABAB	CDCD	true
AAFFG	AAFGF	false
asdasd	qweqwe	true

Answer 1

First, as you did we can compare the size of 2 strings. If they are equal we continue.

By iterating on 1 of the strings we can fill a map. Keys of the map are characters seen in the first string and its value is the corresponding character in the second string.

By reaching the nth character we check that whether we have a key or the same as this character or not.

If yes: Check the value that is equal to the nth character of the second string.

If no: we add a new key-value to the map. (the key is the nth character of the first string and the value is the nth character of the second string)

1. After doing this we should do this again for another string. I mean for example if in the first step characters of the first string were keys, In the second step we should replace the string in the way that characters of second string become keys.

If both of them give true the answer is true. Otherwise false.

2. Rather than replacing strings and repeat the iteration, we can prevent repetitive values to be added to the map.

To understand paragraph 1 and 2 imagine 1 iteration on strings of "ABC" and "ZZZ".

Notice that arrays can be used instead of map.

Answer 2

By 1 iteration on strings create key-value pairs That define corresponding characters.

In the second iteration check whether each character in the first/second string is compatible with the character with equal index in the second/second string. If there is no incompatibility return true, otherwise false.

Answer 3

If we find a new character, we will make it equal to the same position as the other string characters. Next time, if we found it again, we will check based on it.

Suppose we have 'aa' and 'cd'.
1st iteration: 'a'='c'
2nd iteration: already 'a'='c'(1st iteration), so we must need 'c' in our 2nd string.
But in our 2nd string, it is 'd'. so simply it will return false.

#include <bits/stdc++.h>

using namespace std;

// if you want to use map
bool LetterPattern_with_map(string str1,string str2)
{
    if(str1.size()!=str2.size()) return false;
    map<char,char> mp;
    for(int i=0;i<str1.size();i++)
    {
        if(!mp[str1[i]]) { mp[str1[i]]=str2[i]; continue; }
        if(mp[str1[i]]!=str2[i]) return false;
        
    }
    return true;
}

// if you want to use array instead of map
bool LetterPattern_with_array(string str1,string str2)
{
    if(str1.size()!=str2.size()) return false;
    int check[128]={0};
    for(int i=0;i<str1.size();i++)
    {
        if(!check[str1[i]-'A'+1]) { check[str1[i]-'A'+1]=(int)(str2[i]-'A'+1); continue; }
        if(check[str1[i]-'A'+1]!=(int)(str2[i]-'A'+1)) return false;
    }
    return true;
}



int main()
{
    cout << "Please enter two string variable: ";
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Same Letter Pattern: " << LetterPattern_with_map(str1, str2)<<'\n';
    cout << "Same Letter Pattern: " << LetterPattern_with_array(str1, str2);
}

Answer 4

If I understood right and:

AABB - CCDD = true
AAFFG - AAFGF = false
asdasd - qweqwe = true

That's not pattern, it's check if second string is result of encryption by substitution of first. You can do it in simpler way, by attempting to built substitution table. If it fails, i.e. there are more than one association between source and result, the outcome is false.

Simplest case is that we have to check whole string. If we would need to find that if any substring is substitution of pattern contained in second string, that squares the complexity:

#include <string>
#include <vector>
#include <map>
#include <optional>
#include <limits>

bool is_similar (const std::string& s1, const std::string& s2)
{
    if(s1.length() != s2.length()) return false;
    using TCh = std::decay_t<decltype(s1)>::value_type;
    // for non-unicode characters can use an array
    //std::optional<TCh> table[ std::numeric_limits<TCh>::max ];
    // std::optional used for clarity, in reality may use `TCh`
    // and compare with zero char
    std::map< TCh, std::optional<TCh>> table;
    
    for (size_t it = 0; it < s1.length(); ++it)
    {
       if( table[s1[it]].has_value() && table[s1[it]] != s2[it] ) return false;
       if( table[s2[it]].has_value() && table[s2[it]] != s1[it] ) return false;
       table[s1[it]] = s2[it];
       //table[s2[it]] = s1[it]; if symmetric
    }
    return true;
}

Answer 5

A simple (maybe not very efficient) approach:

#include<iostream>
#include<unordered_map>

using namespace std;

int main(void) {
    string s1, s2;
    unordered_map<string, char> subs;

    cout<<"Enter the strings: ";
    cin >> s1 >> s2;
    
    if (s1.length() != s2.length())
        cout<<"False"<<endl;
    else {
        for (int i=0; i<s1.length(); ++i) {
            string key(1, s2[i]);
            subs[key] = s1[i];
        }

        string s1_2 = "";

        for (int i=0; i<s2.length(); ++i) {
            string key(1, s2[i]);
            s1_2 += subs[key];
        }

        if (s1 == s1_2) 
            cout<<"True"<<endl;
        else
            cout<<"False"<<endl;
    }
    return 0;
}

---

Time Complexity O(n); Space Complexity O(n)

Answer 6

Not sure about better, but a C++17 solution that builds a regular expression based on the first string's letters and matches it against the second:

#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <tuple>
#include <regex>

bool match(const std::string &pattern, const std::string &s) {
  std::unordered_map<char, int> indexes;
  std::ostringstream builder;
  int ref = 1;

  for (char c : pattern) {
    if (auto backref = indexes.find(c); backref != indexes.end()) {
      builder << '\\' << backref->second;
    } else {
      if (ref > 1) {
        builder << "(?!";
        for (int n = 1; n < ref; n += 1) {
          if (n != 1) {
            builder << '|';
          }
          builder << '\\' << n;
        }
        builder << ')';
      }
      builder << "(.)";
      indexes.emplace(c, ref++);
    }
  }

  // std::cout << builder.str() << '\n';
  return std::regex_match(s, std::regex{builder.str()});
}

int main() {
  std::tuple<std::string, std::string, bool> tests[] = {
      {"AABB", "CCDD", true},
      {"ABAB", "CDCD", true},
      {"AAFFG", "AAFGF", false},
      {"asdasd", "qweqwe", true},
      {"abc", "zzz", false}
  };

  std::cout << std::boolalpha;
  for (const auto &[s1, s2, expected] : tests) {
    if (match(s1, s2) == expected) {
      std::cout << s1 << " => " << s2 << " = " << expected << ": PASS\n";
    } else {
      std::cout << s1 << " => " << s2 << " = " << (!expected) << ": FAIL\n";
    }
  }

  return 0;
}

Answer 7

And, last but not least, an additional solution using "counting".

If we read the requirement, then you are only interested in a boolean result. That means, as soon as we have a 2nd association for a letter in the first string, then the result is false.

Example: If we have an 'a' and in the 2nd string at the same position a 'b', and then in some next position of the first string again an 'a' but then in the same position of the 2nd string a 'c', then we have 2 different associations for the letter a. And that is false.

If there is only one association per letter, then everything is ok.

How to accomplish "association" and "counting". For the "association, we will use an associative container, a std::unordered_map. And, we associate a letter from the first string, with a std::set of the already processed letters (from the 2nd string). The std::sets iinsert function will not add double letters from the secondt string. So, if there is again a 'b' associated with an 'a', that is completly fine.

But if there is a different associated letter, then the std::set will contain 2 elements. That is an indicator for a false result.

In such case, we stop evaluation characters immediately. This leads to a very compact and fast code.

Please see:

#include <iostream>
#include <string>
#include <unordered_map>
#include <utility>
#include <set>

bool letterPattern(const std::string& s1, const std::string& s2) {

    // Here we will store the result of the function
    bool result{ s1.length() == s2.length() };

    // And here all associations
    std::unordered_map<char, std::set<char>> association{};

    // Add associations. Stop if result = false
    for (size_t index{}; result && index < s1.length(); ++index)
        if (const auto& [iter, ok] {association[s1[index]].insert(s2[index])}; ok)
            result = association[s1[index]].size() == 1;

    return result;
}
// Some driver test code
int main() {
    std::vector<std::pair<std::string,std::string>> testData{
        {"AABB", "CCDD"},
        {"ABAB", "CDCD"},
        {"AAFFG", "AAFGF"},
        {"asdasd", "qweqwe"}
    };

    for (const auto& p : testData)
        std::cout << std::boolalpha << letterPattern(p.first, p.second) << "\t for: '" << p.first << "' and '" << p.second << "'\n";

    return 0;
}

Answer 8

As you want to see if one string is a Caesar cipher of the other, you might do:

bool LetterPatternImpl(const std::string& str1, const std::string& str2) { 
    if (str1.length() != str2.length()) { return false; }

    std::array<std::optional<char>, 256> mapping; // char has limited range,
                                                  // else we might use std::map
    for (std::size_t i = 0; i != str1.length(); ++i) {
        auto index = static_cast<unsigned char>(str1[i]);

        if (!mapping[index]) { mapping[index] = str2[i]; }
        if (*mapping[index] != str2[i]) { return false; }
    }
    return true;
}

bool LetterPattern(const std::string& str1, const std::string& str2) {
    // Both ways needed
    // so ABC <-> ZZZ should return false.
    return LetterPatternImpl(str1, str2) && LetterPatternImpl(str2, str1);
}