力扣127. 单词接龙

〇〇

127. 单词接龙
困难
相关标签
相关企业
字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
示例 2：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[ i].length == beginWord.length
beginWord、endWord 和 wordList[ i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同
通过次数
228.5K
提交次数
465.3K
通过率
49.1%

〇〇

把2个单词都从中间分成2个子串，存在两个子串合并后相等的，就是能转的，然后CTE接龙

〇〇

with recursive q as
(select   'hit' beginWord ,  'cog' endWord,  ['hit','hot','dot','dog','lot','log','cog'] wordList)
,a as(select unnest(wordlist)w,unnest(range(length(wordlist)))n from q where list_has(wordlist,beginWord)
union all
select unnest(wordlist+[beginWord])w,unnest(range(1+length(wordlist)))n from q where not list_has(wordlist,beginWord)
)
,t as (select a.w,b.w w2,a.n,b.n n2 from a,a b where exists(select 1 from range(1,10)t(i) where a.n<>b.n and i<=length(a.w)
and substr(a.w,1,i-1)||substr(a.w,i+1)=substr(b.w,1,i-1)||substr(b.w,i+1)))
,x as (select 1 lv, beginword b,b path,0 m from q
union all
select lv+1, w2 ,path||','||w2, m+(1<< n2) from x,t where x.b=t.w and x.b<> (select endword from q) and m & (1<<n2)=0)
from x where b=(select endword from q) order by lv limit 1;

┌───────┬─────────┬─────────────────────┬───────┐
│  lv   │    b    │        path         │   m   │
│ int32 │ varchar │       varchar       │ int32 │
├───────┼─────────┼─────────────────────┼───────┤
│     5 │ cog     │ hit,hot,lot,log,cog │   114 │
└───────┴─────────┴─────────────────────┴───────┘
Run Time (s): real 0.080 user 0.327602 sys 0.031200

〇〇

用这个测试溢出
q as
(select   '1234' beginWord ,  '9876' endWord,  [x::varchar for x in range(1234,9999)] wordList)

〇〇

如果不加lv<5,这个测试非常慢,怎么让有一个找到就退出递归？
with recursive q as
(select   '1234' beginWord ,  '2345' endWord,  [x::varchar for x in range(1234,2400)] wordList)
,a as(select unnest(wordlist)w,unnest(range(length(wordlist)))n from q where list_has(wordlist,beginWord)
union all
select unnest(wordlist+[beginWord])w,unnest(range(1+length(wordlist)))n from q where not list_has(wordlist,beginWord)
)
,t as (select a.w,b.w w2,a.n,b.n n2 from a,a b where exists(select 1 from range(1,10)t(i) where a.n<>b.n and i<=length(a.w)
and substr(a.w,1,i-1)||substr(a.w,i+1)=substr(b.w,1,i-1)||substr(b.w,i+1)))
--from t;
,x as (select 1 lv, beginword b,b path,[0] m from q
union all
select lv+1, w2 ,path||','||w2, list_append(m,n2) from x,t where lv<5 and x.b=t.w and x.b<> (select endword from q) and list_has(m ,n2)=0)
from x where b=(select endword from q) order by lv limit 1;

〇〇

找能转换的对子就要5秒
with recursive q as
(select   '1234' beginWord ,  '2345' endWord,  [x::varchar for x in range(1234,2400)] wordList)
,a as(select unnest(wordlist)w,unnest(range(length(wordlist)))n from q )
,t as (select a.w,b.w w2,a.n,b.n n2 from a,a b where exists(select 1 from range(1,10)t(i) where a.n<>b.n and i<=length(a.w)
and substr(a.w,1,i-1)||substr(a.w,i+1)=substr(b.w,1,i-1)||substr(b.w,i+1)))
select count(*) from t;

newkid

这个路径权重都是1, 找最短路径用递归WITH是没问题的。
如果加上权重，比如不同的字母个数之类的，那就得用Dijkstra的算法。

newkid

with wlist as (
select to_char(level) as w
from dual
where level>=1234
connect by level<=9999
)
,wl as (
select w
      ,level pos
      ,substr(w,level,1) c
  from wlist
connect by level<=length(w) and prior sys_guid() is not null  and prior w=w
)
,w as (
select w1.w w1,w2.w w2
  from wl w1,wl w2
where w1.pos=w2.pos and w1.c=w2.c and w1.w<>w2.w
group by w1.w,w2.w
having count(*)=max(length(w1.w))-1
)
,t(w2,path,cnt) as (
select w2,w1||','||w2,0
from w where w1='1234'
union all
select w.w2,t.path||','||w.w2
      ,count(case when w.w2='9876' then 1 end) over() cnt
  from t,w
where t.cnt=0
       and t.w2=w.w1
       and instr(t.path,w.w2)=0
)
select path from t where w2='9876' and rownum=1;


PATH
---------------------------
1234,1274,1276,9276,9876

Elapsed: 00:00:18.25

〇〇

count()over求下轮停止很巧妙，having count(*)=length—1也节省了运算