LeetCode: String Transforms Into Another String

Posted on August 5, 2019July 26, 2020 by braindenny

String Transforms Into Another String

Similar Problems:

Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Return true if and only if you can transform str1 into str2.

Example 1:

Input: str1 = "aabcc", str2 = "ccdee"
Output: true
Explanation: Convert 'c' to 'e' then 'b' to 'd' then 'a' to 'c'. Note that the order of conversions matter.

Example 2:

Input: str1 = "leetcode", str2 = "codeleet"
Output: false
Explanation: There is no way to transform str1 to str2.

Note:

1 <= str1.length = str2.length < 10^4
Both str1 and str2 contain only lowercase English letters.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/string-transforms-into-another-string
// Basic Ideas: graph
//   a->c
//   b->d
//   c->e
//
//  The same character of str2 must be the same one in str1
//   Reverse: from str2 to str1
//
//  For change of a list, from end to begin. And the end is unsed in str1
//  For change of a cycle, need a temporary unused character
//
// Complexity: Time O(n), Space O(1)
func canConvert(str1 string, str2 string) bool {
    if str1 == str2 {
        return true
    }
    m := map[int]int{}
    for i, _ := range str1 {
        n1, n2 := int(str1[i]-'a'), int(str2[i]-'a')
        // expecting one character of str2 to map to multiple ones in str1
        if _, ok := m[n1]; ok && m[n1] != n2 {
            return false
        } else {
            m[n1] = n2
        }
    }
    // one unused character in str2
    chars := make([]int, 26)
    cnt := 26
    for _, v := range m {
        if chars[v] == 0 {
            cnt--
        }
        chars[v]++
    }
    return cnt>0
}

Post Views: 0