1

以下是我在leetcode中给出的同构字符串问题的解决方案：

public bool IsIsomorphic(string s, string t)
    {
        int[] s1 = new int[s.Length];
        int[] t1 = new int[t.Length];
        bool isI = true;
        if (s1.Length > 0 && t1.Length > 0)
        {
            s1[0] = 0;
            int i = 1;
            int j = 1;
            for (i = 1; i < s.Length; i++)
            {
                if (s[i] == s[i - 1])
                {
                    s1[i] = 1;
                }
                else
                {
                    s1[i] = 0;
                }
            }
            for (j = 1; j < t.Length; j++)
            {
                if (t[j] == t[j - 1])
                {
                    t1[j] = 1;
                }
                else
                {
                    t1[j] = 0;
                }
            }
            for (int k = 0; k < s1.Length; k++)
            {
                if(s1[k] != t1[k])
                {
                    isI = false;
                }
            }
        }
        else
        {
            isI = true;
        }
        return isI;
    }

它通过了 29/30 个测试用例，但没有通过以下长得离谱的测试用例。与谷歌驱动器中的输入共享代码：

https://docs.google.com/document/d/1UkG8Rc6VItiihwvqzJdM3uMHIX-BCsslJ_lVklkxvq8/edit?usp=sharing

任何帮助都会很棒。

4

1 回答 1

4

好的，因为你没有包括你的算法是如何工作的，让我们做所有的繁重工作，然后我自己去理解它，检查它，并提出另一个更愉快的替代方案。

假设您可能这样做会导致您出错。

您编写算法+猜测您尝试过的内容。

您对每个字符串进行迭代，并且仅检查是否重复出现在同一索引中但在相反的两侧，如果它们是您将它们标记为 1，否则为 0。其他字符串也是如此。当您完成对两个字符串的迭代时，您正在检查这些值是否相等。

这是一个错误的假设。

错误假设＃1：仅放置在 2 个字符上
仅放置在两个数字 0、1 上来表示字符串上的重复是不可能的，因此是不正确的。
当我们有几个重复字符时会发生什么？假设当前算法中的Banana，您不能仅用 2 个字符来表示B、a和n 。
洞察：现在我们明白，对于每个独特的角色，我们都需要新的数字。

错误假设#2：标记重复字符
让我们假设为每个新字符分配一个数字。

  1. 我们如何识别新角色？这意味着我们需要扫描旧字符以查看它是否已经存在，这意味着我们不能对字符串进行一次快速扫描，这意味着我们需要扫描每个当前的 I(index) 字符以查找 0-(I -1) 看看那个词是否已经存在。这导致我们遇到另一个问题，我们有数字而不是实际字符？我们现在在干什么 ？创建另一个数组来保存字符的每个唯一数字？这意味着另一个数组（复杂性和内存）。

  2. 假设我们有 6 个长字符串，您只认为可以通过按索引0,5 |比较值来扫描重复字符 1,4 | 2, 3这不足以确定它们是重复的，因为您正在假设您知道一个字符串中的重复字符应该是什么顺序（索引），这是我们无法预见的。例如：banana => b != a, a != n, n != a 这意味着这个词没有重复字符？这显然是错误的。

正如你所看到的，我们可以闻到一些有趣的事情正在发生，这么小的一部分很麻烦。

如果我们能花更多的时间在如何以更有效的方式解决这个问题上，以及我们拥有的可供处置的工具（我们可以自己制作工具 [Array over Dictionary]）上，这一切都属于设计发现了所有这些问题。

永远投资于设计，值得投资，你不会后悔的。

解决方案#1：
为什么使用数字？让我们使用实际的字符。在这种情况下，另一种解决方案是更好的选择。

public bool IsIsomorphic(string s, string t)
{
    if (s.Length != t.Length)
    {
        return false;
    }

    bool result = true;
    var relation = new Dictionary<char, char>();
    for (int i = 0; i < s.Length; i++)
    {
        char sChar = s[i];
        char tChar = t[i];
        char c;
        if (relation.TryGetValue(sChar, out c))
        {
            if (c != tChar)
            {
                result = false;
                break;
            }
        }
        else if (relation.ContainsValue(tChar))
        {
            result = false;
            break;
        }
        else
        {
            relation.Add(sChar, tChar);
        }
    }
    return result;
}

解决方案#2：
更多的内存，更少的可读性并且不使用外部工具（最后的检查是简单的数组值比较）

public bool IsIsomorphic3(string s, string t)
{
    if (s.Length != t.Length)
    {
        return false;
    }

    int[] firstNumbering = new int[26];
    int[] firstStringOrder = new int[s.Length];
    int firstCounter = 0;
    for (int i = 0; i < s.Length; i++)
    {
        char c = s[i];
        if (firstNumbering[c - 'a'] == 0)
        {
            firstNumbering[c - 'a'] = ++firstCounter;
        }
        firstStringOrder[i] = firstNumbering[c - 'a'];
    }

    int[] secondNumbering = new int[26];
    int[] secondStringOrder = new int[t.Length];
    int secondCounter = 0;
    for (int j = 0; j < t.Length; j++)
    {
        char c = t[j];
        if (secondNumbering[c - 'a'] == 0)
        {
            secondNumbering[c - 'a'] = ++secondCounter;
        }
        secondStringOrder[j] = secondNumbering[c - 'a'];
    }

    return firstStringOrder.SequenceEqual(secondStringOrder); // Comparing values using Linq
}
于 2016-02-11T01:25:27.820 回答