前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode383. Ransom Note

leetcode383. Ransom Note

作者头像
眯眯眼的猫头鹰
发布2019-03-13 16:46:08
3460
发布2019-03-13 16:46:08
举报
文章被收录于专栏:眯眯眼猫头鹰的小树杈

题目

代码语言:javascript
复制
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

假设有一组字母和一组从杂志中获取的字母,问是否能够用从杂志中获取的字母构成想要的那组字母,要求每个单词只能使用一次。

思路一

使用索引为字母的数组来存储该字母还剩下几个没有从杂志中找到。每从杂志中找到一个字母,对应字母位置上的数字减一,每遇到一个字母则该字母位置上的数字加一。如果没有多余的字母,则说明可以找到足够多的字母拼接。

代码语言:javascript
复制
    public boolean canConstruct(String ransomNote, String magazine) {
        if(ransomNote.isEmpty()) return true;
        if(ransomNote.length() > magazine.length()) return false;
        int p1 = 0, p2 = 0;
        int[] count = new int[26];
        int wordCount = 0;
        while(p1 < ransomNote.length() && p2 < ransomNote.length()) {
            char c1 = ransomNote.charAt(p1);
            char c2 = magazine.charAt(p2);
            if(++count[c1-'a'] == 1) {
                wordCount++;
            }
            if(--count[c2-'a'] == 0) {
                wordCount--;
            }
            
            p1++;
            p2++;
        }
        
        while(p2 < magazine.length()) {
            if(wordCount == 0) break;
            char c = magazine.charAt(p2);
            count[c-'a']--;
            if(count[c-'a'] == 0) {
                wordCount--;
            }
            p2++;
        }
        return wordCount == 0;
    }

思路二:找不到字母就结束

思路二利用java的API来查找magazine中从上一个找到的字母开始,下一个字母所在的位置。如果找不到,则说明无法完成拼接。

代码语言:javascript
复制
    public boolean canConstruct(String ransomNote, String magazine) {
        int len=ransomNote.length();
        int[] index = new int[128];
        for(int i = 0; i < len; i++){
            char cu=ransomNote.charAt(i);
            int result=magazine.indexOf(cu,index[cu]);
            if(result == -1){
                return false;
            }
            else{
                index[cu]=result + 1;   
            }   
        }
        return true;
    }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-11-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 思路一
  • 思路二:找不到字母就结束
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档