📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2424| 回复: 2
跳转到指定楼层
上一主题 下一主题
收起左侧

[字符串] 问一道string pattern recognition的题

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
Given a pattern and a string - find if the string follows the same pattern
Eg:
Pattern : "a b b a", input: "cat dog dog cat" should return 1.
Pattern: "aaaa", input: "asdasdasdasd" should return 1.
Pattern: "aabb", input: "xyzabcxzyabc" should return 0.


上一篇:Dijkstra Good Numerals 求解
下一篇:小弟对于冒泡排序最最优情况有些不了解
🔗
chitose 2014-10-25 09:24:17 | 只看该作者
全局:
本帖最后由 hakase 于 2014-10-25 09:26 编辑
  1.     public static boolean matchPattern(String pattern, String target){
  2.         if(pattern.isEmpty()){
  3.             return true;
  4.         }else{
  5.             final int index = target.indexOf(pattern.charAt(0));
  6.             return index == -1 ? false : matchPattern(pattern.substring(1), target.substring(index));
  7.         }
  8.     }
复制代码
另外你的第一个test case应该是“a d d a”;
标准的解应该使用状态机,好麻烦。
回复

使用道具 举报

🔗
chy4483452 2014-10-26 12:28:36 | 只看该作者
全局:
本帖最后由 chy4483452 于 2014-10-26 13:25 编辑

偷懒直接输出true false了. 没做什么优化 抛砖引玉.

unordered_map<char, string> mapping;
bool matchPattern(string pattern, string str) {
    if (pattern.empty() || str.empty())
        return pattern.empty() && str.empty();

    char ch = pattern[0];
    if (ch == ' ')
        if (str[0] == ' ') return matchPattern(pattern.substr(1), str.substr(1));
        else return false;

    if (mapping.find(ch) == mapping.end()) {
        for (int i=1; i<=str.length(); i++) {
            mapping[ch] = str.substr(0, i);
            bool trymatch = matchPattern(pattern.substr(1), str.substr(i));
            if (trymatch) return true;
        }
        mapping.erase(ch);
    } else {
        if (mapping[ch] == str.substr(0, mapping[ch].length()))
            return matchPattern(pattern.substr(1), str.substr(mapping[ch].length()));
        else
            return false;
    }
    return false;
}
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表