精华内容
下载资源
问答
  • LeetCode 字符串的排列

    2019-03-29 16:16:00
    换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 示例2: 输入: s1= "ab" s2 = "eidboaoo" 输出: ...

    给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。

    换句话说,第一个字符串的排列之一是第二个字符串的子串。

    示例1:

    输入: s1 = "ab" s2 = "eidbaooo"
    输出: True
    解释: s2 包含 s1 的排列之一 ("ba").
    

     

    示例2:

    输入: s1= "ab" s2 = "eidboaoo"
    输出: False
    解法:开始想跑dfs 跑全排列,然后用KMP 去匹配,但是后来想了一下,不用那么复杂,因为全是小写字母,所以只需要s2 和s1 这段字符串的字符数量一样就可以了,
    因为s1 的子串可以重新组合,必然能和s2 匹配成功。
    class Solution {
    public:
        bool check(int a[])
        {
            for(int i=0;i<26;i++)
            {
                if(a[i]!=0)
                    return false;
            }
            return true;
        }
        bool checkInclusion(string s1, string s2) {
            int len1=s1.length();int len2=s2.length();
            if(len1>len2 || len1==0 || len2==0)
            {
                return false;
            }
            else
            {
                int a[26]={0};
                for(int i=0;i<len1;i++)
                {
                    a[s1[i]-'a']--;
                    a[s2[i]-'a']++;
                }
                for(int j=len1;j<len2;j++)
                {
                    if(check(a))
                    {
                        return true;
                    }
                    a[s2[j-len1]-'a']--;
                    a[s2[j]-'a']++;
                }
                return check(a);
            }
        }
    };

     

    转载于:https://www.cnblogs.com/jkzr/p/10622052.html

    展开全文
  • leetcode字符串的排列

    2020-03-19 10:24:54
    此题主要需要考虑的是如何去重,当字符串存在重复字符时 1.使用set去重 使用set记录所有的排列,由于set中元素的唯一性,已经存在的元素无法被插入 代码如下: class Solution { public: vector<string>...

     

    此题主要需要考虑的是如何去重,当字符串存在重复字符时

    1.使用set去重

    使用set记录所有的排列,由于set中元素的唯一性,已经存在的元素无法被插入

    代码如下:

    class Solution {
    public:
    
        vector<string> permutation(string s) {
            set<string>tem;
            backtrack(s,0,tem);
            vector<string> ans(tem.begin(),tem.end());
            return ans;
        }
        void backtrack(string s,int start,set<string>&tem)
        {
            if(start == s.size() - 1)
            {
                tem.insert(s);
                return;
            }
            for(int i = start;i < s.size();i++)
            {
                swap(s[start],s[i]);
                backtrack(s,start + 1,tem);
                swap(s[start],s[i]);
            }
        }
    };

    2.排序去重

     

    展开全文
  • Leetcode 字符串的排列

    2018-12-15 20:54:22
    换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba").   示例2: 输入: s1= &...

    给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。

    换句话说,第一个字符串的排列之一是第二个字符串的子串。

    示例1:

    输入: s1 = "ab" s2 = "eidbaooo"
    输出: True
    解释: s2 包含 s1 的排列之一 ("ba").
    

     

    示例2:

    输入: s1= "ab" s2 = "eidboaoo"
    输出: False
    

     

    注意:

    1. 输入的字符串只包含小写字母
    2. 两个字符串的长度都在 [1, 10,000] 之间

     

    不知道为什么,这道题直接用全排列(next_permutation)判子串不行

    百度了一下发现他是要计算区间内字母出现的次数相同就算排列了(黑人问号脸??)

    然后要记得特判s2比s1短的就直接false

    class Solution {
    public:
        bool checkInclusion(string s1, string s2) {
            if(s1.length()>s2.length())
                return false;
            int flag=0;
            int m1[100]={0},m2[100]={0};
            for(int i=0;i<s1.length();i++)
            {
                m1[s1[i]-'a']++;
                m2[s2[i]-'a']++;
            }
            int ff=0;
            for(int i=0;i<30;i++)
            {
                if(m1[i]!=m2[i])
                {ff=1;break;}
            }
            if(!ff)flag=1;
            if(!flag)
            {
                for(int i=s1.length();i<s2.length();i++)
                {
                    m2[s2[i]-'a']++;
                    m2[s2[i-s1.length()]-'a']--;
                    int ff=0;
                    for(int j=0;j<30;j++)
                    {
                        if(m1[j]!=m2[j])
                        {ff=1;break;}
                    }
                    if(!ff){flag=1;break;}
                }
            }
            if(flag)return true;
            else return false;
        }
    };

     

    展开全文
  • 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 示例2: 输入: s1= "ab" s2 = "eidboaoo" 输出: False ...

    给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。

    换句话说,第一个字符串的排列之一是第二个字符串的子串。

    示例1:
    
    输入: s1 = "ab" s2 = "eidbaooo"
    输出: True
    解释: s2 包含 s1 的排列之一 ("ba").
     
    
    示例2:
    
    输入: s1= "ab" s2 = "eidboaoo"
    输出: False
     
    

    注意:

    输入的字符串只包含小写字母
    两个字符串的长度都在 [1, 10,000] 之间

    1 初始化滑动窗口,其长度为s1的长度
    2 只需要判断滑动窗口中字母出现的频率是否与s1相同即可
    3 利用哈希表储存s1中字母出现的频率,利用count总计数判断是否已经匹配
    4 不断滑动窗口,分别对离开窗口和进入窗口的字母进行哈希表加减操作和count加减操作。

    class Solution:
        def checkInclusion(self, s1: str, s2: str) -> bool:
            if len(s1) > len(s2):
                return False
            dic_1 = {k:0 for k in string.ascii_lowercase}
            dic_2 = {k:0 for k in string.ascii_lowercase}
            for i in s1:
                dic_1[i] += 1
            
            for j in range(len(s2)):
                dic_2[s2[j]] += 1
    
                if j >= len(s1):
                    dic_2[s2[j-len(s1)]] -= 1
    
                if dic_1 == dic_2:
                    return True
            
            return False
    
    
    
    
    class Solution:
        def checkInclusion(self, s1: str, s2: str) -> bool:
            len_1, len_2 = len(s1), len(s2)
            if len_1 > len_2:
                return False
            char_count_1 = [0 for i in range(26)]
            char_count_2 = char_count_1.copy()
            ascii_a = ord('a')
            for i in range(len_1):
                char_count_1[ord(s1[i]) - ascii_a] += 1
                char_count_2[ord(s2[i]) - ascii_a] += 1
            for i in range(len_1, len_2):
                if self.isEqual(char_count_1, char_count_2):
                    return True
                char_count_2[ord(s2[i - len_1]) - ascii_a] -= 1
                char_count_2[ord(s2[i]) - ascii_a] += 1
            return self.isEqual(char_count_1, char_count_2)
    
        def isEqual(self, char_count_1, char_count_2):
            for i in range(26):
                if char_count_1 != char_count_2:
                    return False
            return True
    
    
    
    展开全文
  • 字符串的排列 给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = “ab” s2 = “eidbaooo” 输出: True 解释: s2 ...
  • 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 示例2: 输入: s1= "ab" s2 = "eidboaoo" 输出: False 相似...
  • 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 示例2: 输入: s1= "ab" s2 = "eidboaoo" 输出: False 注意: ...
  • 首字母+其余字符串的全排列,直到其余字符串长度为1返回。 最终利用list(set(lst))对lst去重。 理解简单,书写便捷,缺点是耗时较久。 class Solution: #递归 def permutation(self, s: str): i...
  • 字符串的排列本题从逻辑上可以分成 5 个部分:检查重复的元素交换元素终止条件其中交换元素需要在递归下去做,答案class Solution: def permutation(self, s: str) -> List[str]: # 深度遍历 def dfs(n): # 终止...
  • 使用滑动窗口方法, 总体思路就是,首先因为字符串输入都是a-z小写字母, 首先为两个字符串创建两个相对应数组, 可以通过ascall码-a差值存放每个字符串中字母出现以及次数 先通过比较s2中最左端开始...
  • LeetCode 567 字符串的排列 题目链接 给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例 1: 输入: s1 = "ab" s2 = "eidbaooo" ...
  • leetcode字符串的排列 题目描述: 给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: ...
  • leetcode567字符串的排列 给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = “ab” s2 = “eidbaooo” 输出: ...
  • Leetcode 567 字符串的排列

    千次阅读 2021-02-10 11:46:20
    换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 示例2: 输入: s1= "ab" s2 = "eidboaoo" 输出: False ...
  • 字符串的排列 题意: **给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = “ab” s2 = “eidbaooo” 输出: True ...
  • 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = “ab” s2 = “eidbaooo” 输出: True 解释: s2 包含 s1 的排列之一 (“ba”). 示例2: 输入: s1= “ab” s2 = “eidboaoo” 输出: False...
  • leetcode-字符串的排列

    2020-07-04 23:02:12
    字符串的排列和数字的排列都属于回溯的经典问题 回溯算法框架:解决一个问题,实际上就是一个决策树的遍历过程: 路径:做出的选择 选择列表:当前可以做的选择 结束条件:到达决策树底层,无法再做选择...
  • 字符串的排列>>> 滑动窗口 class Solution { public boolean checkInclusion(String s1, String s2) { Character[] s1Aray = new Character[s1.length()]; Character[] s2Aray = new Character[s2....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,162
精华内容 1,264
关键字:

leetcode字符串的排列