String Transforms Into Another String - CPP Solution

1. Introduction

This blog post explores a more complex string manipulation problem in C++: determining whether one string can transform into another through a series of character replacements. This problem is a great way to understand the concepts of mapping and character transformation in strings.

Problem

Given two strings str1 and str2, we need to find out if it is possible to transform str1 into str2 by replacing zero or more characters in str1. Each character can be replaced only with one specific character, and no two characters can map to the same character unless they are the same character.

2. Solution Steps

1. Check if str1 and str2 are of the same length. If not, return false.

2. Create a map to store the mapping of characters from str1 to str2.

3. Iterate through the characters of str1 and str2 simultaneously.

4. For each character in str1, map it to the corresponding character in str2.

5. If a character in str1 is already mapped to a different character, return false.

6. After the iteration, check if a cycle is formed in the mapping that makes the transformation impossible.

7. Return true if the transformation is possible.

3. Code Program

#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

// Function to check if str1 can be transformed into str2
bool canConvert(string str1, string str2) {
    if (str1 == str2) return true;
    if (str1.length() != str2.length()) return false;

    unordered_map<char, char> charMap;
    for (int i = 0; i < str1.length(); i++) {
        // Check for conflicting mappings
        if (charMap.count(str1[i]) && charMap[str1[i]] != str2[i]) {
            return false;
        }
        charMap[str1[i]] = str2[i];
    }

    // Check for cycle in mapping
    return unordered_set<char>(str2.begin(), str2.end()).size() < 26;
}

int main() {
    string str1 = "aabcc", str2 = "ccdee";
    cout << "Can transform: " << canConvert(str1, str2) << endl;
    return 0;
}

Output:

Can transform: 1

Explanation:

1. The input strings "aabcc" and "ccdee" are processed to determine if a transformation is possible.

2. A map is created to store the transformation of each character from str1 to str2.

3. The function iterates over the strings and maps characters from str1 to str2.

4. It checks for any conflicting mappings, where one character in str1 would need to transform into two different characters in str2.

5. Since all characters in str1 can be uniquely mapped to characters in str2 and there's no cycle in the mapping (there's at least one character in the target alphabet not used in str2), the transformation is possible.

6. The function returns true (represented as 1), indicating the possibility of transformation.