时间戳

首页 > 解决方案 > 大海捞针“gfg 中的编码问题”

python - 大海捞针“gfg 中的编码问题”

问题描述

qsn 身体：-

给定 2 个字符串 Needle 和 Haystack。给定的 Needle 本质上是扭曲的，可以按任何顺序重新排列和重新排列。您必须检查 Needle 是否是 Haystack 的一部分。即 - 给定的字符串 needle 是否是字符串 haystack 的混洗子字符串。

输入：输入的第一行包含测试用例的数量 T。对于每个测试用例，第一行由针组成，第二行由干草堆组成。

输出：如果给定的字符串 needle 是 haystack 的混洗子字符串，则打印 Yes。否则打印编号。

你的任务：完成函数 isShuffledSubstring()，它将给定的 needle 和 haystack 作为输入并返回一个布尔值。

约束：1 <= haystack.length() <= 1000 1 <= needle.length() <= 1000

例子：

样本输入：

onetwofour hellofourtwooneworld

roseyellow yellow

geekforgeeks ekegorfkeegsgeek

样本输出：

Yes

No

Yes

解释：

测试用例 1：

needleonetwofour可以重新排列为fourtwoonehaystack 的子字符串hellofourtwooneworld。

测试用例 2：

针的长度大于干草堆。因此，needle 不是 haystack 的子串。

测试用例 3：

needlegeekforgeeks可以重新排列为orfkeegsgeekhaystack 的子字符串ekegorfkeegsgeek。

**必需功能 ==:- **

def isShuffledSubstring(needle, haystack): 
    # Your code goes here
    if len(needle)>len(haystack):
        return False
    Map1={}
    Map2={}
    for i in needle:
        if i in Map1:
            Map1[i]+=1
        else:
            Map1[i]=1
    for i in haystack:
        if i in Map2:
            Map2[i]+=1
        else:
            Map2[i]=1
    for i in Map1:
        if i in Map2:
            if Map2[i]<Map1[i]:
                return False
        else:
            return False
    return True

它通过了测试用例，但没有通过完整的测试用例。对不起，所有的测试用例都不是我的，因为它是编码竞赛的一部分。

谢谢你！

标签： python

解决方案

bool check(unordered_map<char,int> &_map)
{
    bool flag = true;
    for(auto i = _map.begin(); i!= _map.end(); i++)
    {
        if(i->second !=0)
        {
            flag = false;
            break;
        }
    }
    return flag;
}

bool isShuffledSubstring(string needle, string haystack) 
{
    int len1 = needle.length();
    int len2 = haystack.length();

    if(len1>len2)
    {
        return false;
    }

    unordered_map<char,int> _map;

    for(int i=0;i<len1;i++)
    {
        if(_map.find(needle[i]) == _map.end())
        {
            _map.insert(make_pair(needle[i],1));
        }
        else
        {
            _map[needle[i]] +=1;
        }

    }

    for(int i=0;i<len1;i++)
    {
        if(_map.find(haystack[i]) != _map.end())
        {
            _map[haystack[i]] -=1;
        }

    }
    if(check(_map))
    {
         return true;
    }

    int i = 0;
    int j= len1;

    while(j<len2)
    {
        if(_map.find(haystack[i]) != _map.end())
        {
                _map[haystack[i]] +=1;
        }
        if(_map.find(haystack[j]) != _map.end())
        {
            _map[haystack[j]] -= 1;
           if(check(_map))
            {
                return true;
            }
        }
       i++;
       j++;
    }
   return false;
}

推荐阅读