比较两个数组和return第一次出现的索引

Question

我有一个任务要做，我一直在想，但我没有想出正确的答案。

In a language of your choosing, write a function that gets a string named str and a string named set.

The function will return the index of the first appearance of any char from set in str.

For example: str = "hellohellohellohelloistom!" set = "t98765!"

The function will return 22 (index of '5' in str). Make sure that time complexity is not larger than the length of both strings - O(m+n) Assume that the string only contains ASCII characters.

我在想，我想分而治之。我有一个始终为 O(1) 的基本情况，我将问题分成更小的问题，直到得到答案。问题是，使用该解决方案，复杂度将为 O(log n)。

我认为的另一种方法是制作一套。但我仍然不知道如何解决这个问题。有什么想法吗？？

Answer 1

这个程序写在Swift

let str = "hellohellohellohelloistom!"
let set = "t98765!"

func findFirstAppearance(str : String , set : String) -> Int? {
    var index : Int?

mainLoop: for setCharacter in set.characters{

    for (indexOfChar,strCharacter) in str.characters.enumerate(){

        if strCharacter == setCharacter{
        index = indexOfChar
            break mainLoop
        }
    }

}

return index
}

print(findFirstAppearance(str, set: set))
print(findFirstAppearance("helloWorld", set: "546Wo"))

或者另一种更省时的解决方案

let str = "hellohellohellohelloistom!"
let set = "t98765!"

func findFirstAppearance(str : String , set : String) -> Int? {
    var index : Int?

    mainLoop: for setCharacter in set.characters{

        if let range = str.rangeOfString(String(setCharacter)){

            index = str.startIndex.distanceTo(range.startIndex)

            break
        }

    }

    return index
}

print(findFirstAppearance(str, set: set))
print(findFirstAppearance("helloWorld", set: "546Wo"))

注：

如果没有找到任何字符，那么它将 return nil
区分大小写比较

希望这能解决您的问题。

Answer 2

由于所有涉及的字符串仅包含 ASCII 字符，因此使用 constant memory 这可以在 O(LengthOf(str) + LengthOf(set)) 中解决。

这里是 "C" 语言的代码：

//ReturnValues:
//-1 : if no occurrence of any character of set is found in str
//value >=0 : index of character in str.
int FindFirstOccurenceOfAnyCharacterInSet(const char *str, const char *set, int *index_of_set)
{
    char hash[256];
    int i = 0;
    while(i < 256)
    {
        hash[i] = -1;
        ++i; 
    }
    i = 0;
    while(set[i] != '[=10=]')    
    {
        hash[set[i]] = i;
        ++i;
    }
    i = 0;
    while(str[i] != '[=10=]')
    {
        if(hash[str[i]] != -1)
        {
            *index_of_set = hash[str[i]];
            return i;
        }
        ++i;
    }
    *index_of_set = -1;
    return -1;
}

逻辑的工作原理是记录set中所有字符的position/indexes（>=0）到hashtable中，然后解析str 并检查 str 的当前字符是否出现在 hash table.

中

index_of_set 还将报告在 str 中找到的 set 中的字符索引。如果 index_of_set = -1 则没有找到。

Answer 3

感谢帮助！！

这里也是C#中的代码。

干杯，

public static int FindFirstOccurenceOfAnyCharacterInSet(string str, string set)
    {
        var hash = new int[256];
        int i = 0;
        while (i < 256)
        {
            hash[i] = -1;
            ++i;
        }
        i = 0;
        do
        {
            hash[set[i]] = i;
            ++i;
        } while (set[i] != '[=10=]' && i < set.Length - 1);
        i = 0;
        while (str[i] != '[=10=]')
        {
            if (hash[str[i]] != -1)
            {
                return i;
            }
            ++i;
        }
        return -1;
    }

比较两个数组和return第一次出现的索引

Compare two arrays and return the index of the first appearence

arrays

complexity-theory

time-complexity