首页 > 其他分享 >【双端广搜】字符串接龙

【双端广搜】字符串接龙

时间:2024-10-31 11:48:00浏览次数:1  
标签:return int 双端 st bfs start 接龙 字符串 size

110. 字符串接龙

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

const int N = 510;

int n;
string word[N];
// 如果两个队列共用st数组,那么两个队列永远不会碰头
// 因为在入队时我们会continue掉st为true的元素
// 而st为true时可能是另一个队列遍历掉的元素
unordered_map<string,bool> state, rstate;
unordered_map<string,int> d, rd;

int bfs(queue<string> &q, unordered_map<string,int> &dist,
    unordered_map<string,int> &rdist,
    unordered_map<string,bool> &st)
{
    auto cur = q.front();   q.pop();
    for(int i = 0; i < cur.size(); i ++ ) 
    {
        for(int j = 0; j < 26; j ++ )
        {
            string t = cur;       
            t[i] = 'a' + j;
            if(st[t]) 
            {
                q.push(t);
                dist[t] = dist[cur] + 1;
                st[t] = false;
                if(rdist[t])   return dist[t] + rdist[t] - 1;
            }
        }
    }
    return 0; // not found
}

int double_direction_bfs(string start, string goal)
{
    if(start == goal)   return 1;
    queue<string> q, rq;
    q.push(start);
    rq.push(goal);
    d[start] = 1;
    rd[goal] = 1;
    state[start] = false;
    rstate[goal] = false;
    // 每次只执行一个队列的bfs,优先执行队列中元素少的
    while(q.size() && rq.size())
    {
        int r;
        if(q.size() < rq.size())    r = bfs(q, d, rd, state);
        else r = bfs(rq, rd, d, rstate);
        if(r)   return r;
    }
    return 0;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n + 2; i ++ )
    {
        cin >> word[i];
        state[word[i]] = true;
        rstate[word[i]] = true;
    }
    cout << double_direction_bfs(word[0], word[1]) << endl;
    return 0;
}

标签:return,int,双端,st,bfs,start,接龙,字符串,size
From: https://www.cnblogs.com/ALaterStart/p/18517431

相关文章

  • 字符串数组转换为整数数组
    在C#中,可以使用Array.ConvertAll方法来将字符串数组转换为整数数组。classProgram{staticvoidMain(string[]args){//案例1://使用Array.ConvertAll方法将字符串数组转换为整数数组//情况1:当确定每个数值......
  • Leetcode每日一题C之3211. 生成不含相邻零的二进制字符串
    1、执行结果:通过2、显示详情:3、题目:  给你一个正整数 n。如果一个二进制字符串 x 的所有长度为2的子字符串中包含 至少 一个 "1",则称 x 是一个 有效 字符串。返回所有长度为 n 的 有效 字符串,可以以任意顺序排列。示例1:输入: n=3输出: ["010","01......
  • Leetcode每日一题C之3216. 交换后字典序最小的字符串
     1、执行结果:通过2、显示详情:3、题目:  给你一个仅由数字组成的字符串 s,在最多交换一次 相邻 且具有相同 奇偶性 的数字后,返回可以得到的字典序最小的字符串。如果两个数字都是奇数或都是偶数,则它们具有相同的奇偶性。例如,5和9、2和4奇偶性相同,而6和9奇偶......
  • 华为OD机试 E卷|字符串分割转换
    华为OD机试E卷|字符串分割转换0、关于本专栏&刷题交流群本文收录于专栏【2024华为OD机试真题】,专栏共有上千道OD机试真题,包含详细解答思路、与四种代码实现(Python、Java、C++、JavaScript)。点击文末链接加入【华为OD机试交流群】,和群友一起刷题备考。刷的越多,考试中遇到原题的......
  • 华为OD机试 E卷|字符串变换最小字符串
    华为OD机试E卷|字符串变换最小字符串0、关于本专栏&刷题交流群本文收录于专栏【2024华为OD机试真题】,专栏共有上千道OD机试真题,包含详细解答思路、与四种代码实现(Python、Java、C++、JavaScript)。点击文末链接加入【华为OD机试交流群】,和群友一起刷题备考。刷的越多,考试中遇到......
  • 字符串散列表暂存
    #include<iostream>#include<string>usingnamespacestd;constintN=10010;//A65---0inta[N];stringv[510];intHash(constint*Key,intTableSize){ unsignedlonginth=0; for(inti=0;i<3;i++) { h=(h<<5)......
  • 根据字符串,获取实体属性上的annotation,如:createTime” 找到对应实体属性中的 TableFi
    根据字符串,获取实体属性上的annotation,如:createTime”找到对应实体属性中的TableField(value="create_time",fill=FieldFill.INSERT)Field[]fields=clazz.getFields();//仅能获取类(及其父类)public属性成员Field[]declaredFields=clazz.getDeclaredFields();......
  • 百度二面算法:合法的括号字符串(贪心解法)
    目录标题1.题目1.1示例2.利用贪心算法求解2.1代码结构分析2.1.1代码优缺点2.1.2星号的角色分析2.1.2.1处理星号的逻辑2.1.2.2整体逻辑2.1.2.3代码逻辑总结2.2贪心的策略体现2.2.1贪心策略的应用1.题目给定一个字符串s,字符串......
  • 算法学习笔记6: 字符串
    字符串字符串哈希通过求解字符串前缀的哈希值的方式,可以比较字符串内任意字串的相等情况。首先需要把每个字符映射成数字,是什么无所谓(因为字符不好计算哈希值呀),然后类似于计算前缀和的方式,这里是计算h[i]表示前i个字符的哈希值。然后把要计算的每个前缀字符串看作是一个P......
  • 【C++】string 类深度解析:探秘字符串操作的核心
     快来参与讨论......