Type Challenges: 21104-medium-findall Solution

/* 21104 - FindAll

by tunamagur0 (@tunamagur0) #medium #template-literal #string

Question

Given a pattern string P and a text string T, implement the type FindAll<T, P> that returns an Array that contains all indices (0-indexed) from T where P matches.

View on GitHub: https://tsch.js.org/21104 */

/* _____________ Your Code Here _____________ */ type StringLength<Text extends string, Chars extends unknown[] = []> = Text extends ${string}${infer Rest} ? StringLength<Rest, [...Chars, unknown]> : Chars['length']

//////////////////

type RemoveFirst = TString extends ${string}${infer Rest} ? Rest : TString type TakeFirst = TString extends ${infer First}${string} ? First : never;

type StringsEq<TLeft extends string, TRight extends string> = StringLength extends StringLength ? TLeft extends TRight ? TRight extends TLeft ? true : false : false : false // type StringsEq<TLeft extends string, TRight extends string> = TLeft extends TRight ? true : never

type FindAll<TString extends string, TSubstring extends string, TIndexes extends number[] = [], TTraversed extends string = '', TToTraverse extends string = TString> = // StringLength extends 0 ? [] : TSubstring extends "" ? [] : // if we traversed everything StringsEq<TString, TTraversed> extends true ? TIndexes // if string start with substring : TToTraverse extends ${TSubstring}${string} ? FindAll<TString, TSubstring, [...TIndexes, StringLength], ${TTraversed}${TakeFirst<TString>}, RemoveFirst> // if string doesnt start with substring but there's possibility that substring is somewhere later in string : TToTraverse extends ${string}${string} ? FindAll<TString, TSubstring, TIndexes, ${TTraversed}${TakeFirst<TString>}, RemoveFirst> : TIndexes

/* _____________ Test Cases _____________ */ import type { Equal, Expect } from '@type-challenges/utils'

type cases = [ Expect<Equal<FindAll<'Collection of TypeScript type challenges', 'Type'>, [14]>>, Expect<Equal<FindAll<'Collection of TypeScript type challenges', 'pe'>, [16, 27]>>, Expect<Equal<FindAll<'Collection of TypeScript type challenges', ''>, []>>, Expect<Equal<FindAll<'', 'Type'>, []>>, Expect<Equal<FindAll<'', ''>, []>>, Expect<Equal<FindAll<'AAAA', 'A'>, [0, 1, 2, 3]>>, Expect<Equal<FindAll<'AAAA', 'AA'>, [0, 1, 2]>>, ]

/* _____________ Further Steps _____________ / /

Share your solutions: https://tsch.js.org/21104/answer View solutions: https://tsch.js.org/21104/solutions More Challenges: https://tsch.js.org */

Solution by DJanocha #36150

타입스크립트에서 문자열 T와 패턴 P가 주어졌을 때, P가 T 내에서 등장하는 모든 위치(0-인덱스 기준)를 반환하는 FindAll<T, P> 타입을 구현하는 문제입니다.

type Test1 = FindAll<'hello hello', 'hello'>; // [0, 6]
type Test2 = FindAll<'abcdef', 'cd'>; // [2]
type Test3 = FindAll<'aaaa', 'aa'>; // [0, 1, 2]
type Test4 = FindAll<'abcdef', 'z'>; // []

이 문제는 타입스크립트의 재귀적인 조건부 타입(Recursive Conditional Types) 을 활용하여 해결할 수 있습니다. 문자열을 한 글자씩 탐색하면서 P가 T 내에서 등장하는 모든 위치를 찾아야 합니다.

T를 처음부터 순차적으로 탐색하면서 P가 일치하는 위치를 찾습니다. P가 T의 현재 위치에서 시작하는 경우, 해당 인덱스를 결과 배열에 추가합니다. 한 글자씩 이동하면서 P의 매칭 여부를 계속 확인합니다. P가 빈 문자열("")이면 찾을 수 있는 위치가 없으므로 []을 반환합니다.

type NormalFindAll<
  T extends string, 
  S extends string,
  P extends any[] = [],
  R extends number[] = [],
> = 
T extends `${string}${infer L}`?
  T extends `${S}${string}`?
    NormalFindAll<L,S,[...P,0],[...R,P['length']]>
    :NormalFindAll<L,S,[...P,0],R>
  :R

type FindAll<
  T extends string, 
  P extends string,
> = 
P extends ''?
  []:NormalFindAll<T,P>

Solution by adultlee #35837

// your answers
type SL<S extends string, LA extends string[] = []> = 
  S extends `${infer F}${infer R}`
    ? SL<R, [...LA, F]>
    : LA['length']

type FindAll<T extends string, P extends string, Indi extends any[] = [], Prefix extends string = ''> = 
  P extends '' 
    ? []
    : T extends `${infer F}${P}${infer R}`
      ? P extends `${infer PF}${infer PR}`
        ? FindAll<`${PR}${R}`, P, [...Indi, SL<`${Prefix}${F}`>], `${Prefix}${F}${PF}`>
        : never
      : Indi

Solution by lxxorz #35824

type FindAll<T extends string, P extends string, J extends string = P extends `${infer J}${any}` ? J : '', L extends string = ''>
  = T extends `${L}${infer M}${P & `${any}${any}`}${any}`
    ? [Count<`${L}${M}`>, ...FindAll<T, P, J, `${L}${M}${J}`>]
    : []

type Count<T extends string, O extends true[] = []> = T extends `${any}${infer R}` ? Count<R, [...O, true]> : O['length']

Playground

Solution by teamchong #35475

type FindAll<T extends string, P extends string, Count extends any[] = [], A extends any[] = []> = P extends ''
  ? []
  : T extends `${string}${infer Rest}`
    ? T extends `${P}${string}`
      ? FindAll<Rest, P, [...Count, 0], [...A, Count['length']]>
      : FindAll<Rest, P, [...Count, 0], A>
    : A;

Solution by wendao-liu #35113

type FindAll<T extends string, P extends string, U extends 1[] = []> = P extends '' ? [] : T extends `${string}${infer rest}` ? 
[
  ...(T extends `${P}${string}` ? [U['length']] : []),
  ...FindAll<rest, P, [...U, 1]>
] : []

Solution by ouzexi #34146

// your answers
type StringLength<T extends string, Res extends any[] = []> = T extends `${infer A}${infer R}` ? StringLength<R, [...Res, A]> : Res['length']

type SplitString<T extends string, Res extends any[] = []> = T extends `${infer A}${infer R}` ? [A, R] : T

type FindAll<T extends string, P extends string, Visit extends string = '', Res extends any[] = []> = 
  P extends '' ? [] :
    T extends `${infer A}${P}${infer R}` ? 
    SplitString<P> extends [infer X extends string, infer Y extends string] ? 
      FindAll<`${Y}${R}`, P, `${Visit}${A}${X}`, [...Res, StringLength<`${Visit}${A}`>]> 
      : FindAll<R, P, `${Visit}${A}${P}`, [...Res, StringLength<`${Visit}${A}`>]>
    : Res

Solution by heyuelan #33878

如果第二个参数是空字符，返回 []
用一个辅助数组来保存当前索引，一个辅助数组用来保存模板模板出现的索引
遍历字符串，判断当前字符串是否是以目标模板作为开始
- 如果是，保存，继续遍历后面的字符
- 如果不是，继续遍历后面的字符
遍历完毕，返回保存模板的辅助数组

type FindAll<T extends string, P extends string, C extends any[] = [], U extends any[] = []> = P extends ""
  ? []
  : T extends `${string}${infer R}`
  ? T extends `${P}${string}`
    ? FindAll<R, P, [...C, 1], [...U, C["length"]]>
    : FindAll<R, P, [...C, 1], U>
  : U;

Solution by tototi5997 #33662

wrong solution when meet FindAll<'AAAA','AA'>


type StringLength<S, Arr extends any[] = []> = S extends `${string}${infer R}`
  ? StringLength<R, [...Arr, 1]>
  : Arr['length'];

type FindAll<
  T extends string,
  P extends string,
  PreStr = '',
  Ret extends number[] = []
> = P extends ''
  ? []
  : T extends `${infer Head}${P}${infer Tail}`
  ? FindAll<
      Tail,
      P,
      `${PreStr & string}${Head}${P}`,
      [...Ret, StringLength<`${PreStr & string}${Head}`>]
    >
  : Ret;

need to prase char one by one

type FindAll<
 T extends string,
 P extends string,
 PreStrArr extends any[]  =  [],
 Ret extends number[] = []
> = 
P extends ''
 ? []
 : T extends `${string}${infer R1}`
 		? T extends `${P}${infer _}` 
   				? FindAll<R1, P, [...PreStrArr, any], [...Ret, PreStrArr["length"]]>
   				: FindAll<R1, P, [...PreStrArr, any], Ret>
   		: Ret

Solution by sunupupup #33478

// your answers
type FirstCharOf<S extends string> = S extends `${infer C}${any}` ? C : ''
type LengthOf<S extends string, Result extends 0[] = []> = S extends `${any}${infer Rest}`
  ? LengthOf<Rest, [0, ...Result]>
  : Result['length']
type FindAll<T extends string, P extends string, Result extends number[] = [], Scanned extends string = ''> = P extends ''
  ? []
  : T extends `${Scanned}${infer Head}${P}${infer Tail}`
    ? FindAll<T, P, [...Result, LengthOf<`${Scanned}${Head}`>], `${Scanned}${Head}${FirstCharOf<P>}`>
    : Result

Solution by DevilTea #33257

// your answers
type Split<T extends string> = T extends `${infer FirstLetter}${infer Rest}` ? [FirstLetter, ...Split<Rest>] : [];
type StringLength<T extends string> = Split<T>['length'];
type Push<T extends any[], P = any> = [...T, P];
type NTuple<N extends number ,P extends any[] = []> = P['length'] extends N ? P : NTuple<N, Push<P, any>>;
type Add<T extends number, P extends number> = [...NTuple<T>, ...NTuple<P>]['length'];
type ToNumber<T> = T extends number ? T : never;

type RemoveFirstLetter<T extends string> = T extends `${infer F}${infer Rest}` ? Rest : '';

type FindAll<T extends string, P extends string, N extends number = 0> = 
  P extends ''
  ? []
  : T extends `${infer Front}${P}${infer Rest}` 
    ? [Add<StringLength<Front>, N>, ...FindAll<`${RemoveFirstLetter<P>}${Rest}`, P, ToNumber<Add<ToNumber<Add<N, 1>>, StringLength<Front>>>>] 
    : [];

Solution by kakasoo #32718

type LengthOfString<
  S extends string,
  T extends string[] = []
> = S extends `${infer F}${infer R}`
  ? LengthOfString<R, [...T, F]>
  : T["length"];

type FindAll<
  T extends string,
  P extends string,
  L extends string = ""
> = P extends ""
  ? []
  : T extends `${infer F}${P}${infer R}`
  ? P extends `${infer U}${infer V}`
    ? [LengthOfString<`${L}${F}`>, ...FindAll<`${V}${R}`, P, `${L}${F}${U}`>]
    : never
  : [];

Solution by vangie #32198

type FindAll<
  T extends string,
  P extends string,
  Before extends number[] = [],
> =
  P extends ''
    ? []
    : T extends `${infer _First}${infer Rest}`
      ? [
        ...(T extends `${P}${infer _Rest}` ? [Before['length']] : []),
        ...FindAll<Rest, P, [...Before, 0]>,
      ]
      : []

Solution by drylint #32078

// your answers

type GetStringLength<T extends string, C extends any[] = []> = T extends `${string}${infer O}` ? GetStringLength<O, [1, ...C]> : C['length'];
type FindAll<T extends string, P extends string, U extends string = ''> = P extends '' ? [] : 
  T extends `${U}${infer S}${P}${string}` ? [GetStringLength<`${U}${S}`>, ...FindAll<T, P, `${U}${S}${P extends `${infer O}${string}` ? O : ''}`>] : [];

Solution by tarotlwei #31749

type FindAll<
  T extends string,
  P extends string,
  L extends 0[] = [],
> = P extends ''
  ? []
  : T extends `${string}${infer R}`
    ? [
        ...(T extends `${P}${string}` ? [L['length']] : []),
        ...FindAll<R, P, [0, ...L]>,
      ]
    : []

Solution by FlareZh #31533

type FindAll<
  T extends string,
  P extends string,
  L extends unknown[] = [],
  R extends string = T extends `${string}${infer Rest}` ? Rest : ''
> = P extends ''
  ? []
  : T extends ''
  ? []
  : T extends `${P}${string}`
  ? [L['length'], ...FindAll<R, P, [...L, unknown]>]
  : FindAll<R, P, [...L, unknown]>;

Solution by bigcreate #31090

// your answers
type FindAll<T extends string, P extends string, Index extends unknown[] = []> = P extends '' ? [] : T extends `${infer F}${infer Rest}` ?[ ...(T extends `${P}${string}` ? [Index["length"]] : []), ...FindAll<Rest, P, [never, ...Index]>] : []

Solution by Kakeru-Miyazaki #30917

// your answers
// 拆分字符串
type Split<T extends string, S extends string = ''> = T extends `${infer P}${S}${infer L}`
 ? [P , ...Split<L, S>]
 : T extends '' ? [] : [T]

// 移除重复
type Deduplication<T, R extends any[] = [], M = never> = T extends [infer F, ...infer L]
  ? [F] extends [M]
    ? Deduplication<L, R, M>
    : Deduplication<L, [...R, F], M | F>
  : R

// 移除头部字符
type RemoveTheHead<T extends string> = T extends `${infer _}${infer S}` ? S : ''

type IndexOfAll<P extends unknown[], S extends string, T extends string, I extends [] = []> =
  T extends ''
    ? I
    : S extends `${infer F}${T}${infer _}`
      ? [...I, [...P, ...Split<F>]['length'], ...IndexOfAll<[...P, unknown], RemoveTheHead<S>, T, I>] // 递归逐步往后移动一步查找
      : I

type FindAll<T extends string, P extends string> = Deduplication<IndexOfAll<[], T, P>> // 移除重复

Solution by milletlovemouse #30902

type FindAll<T extends string, P extends string, U extends any[] = [], O extends any[] = []> = P extends '' ? O : T extends `${string}${infer B}` ? T extends `${P}${string}` ? FindAll<B, P, [...U, 0], [...O, U['length']]> : FindAll<B, P, [...U, 0], O> : O

Solution by dreamluo-plus #30694


type StrLength<T, Len extends unknown[] = []> = T extends `${string}${infer R}`
  ? StrLength<R, [...Len, unknown]>
  : Len['length']

type RemoveFirstWord<T> = T extends `${infer _}${infer L}` ? L : never

type FindAll<T extends string, P extends string, Arr extends number[] = []> = P extends ''
  ? []
  : T extends `${infer L}${P}${infer R}`
    ? FindAll<`${L}_${RemoveFirstWord<P>}${R}`, P, [...Arr, StrLength<L>]>
    : Arr

Solution by XkSuperCool #30355

This might look bit lengthy and probably isn't the smartest answer compared with the others but it should be east to understand. The main idea is to use the util type StrLen and SliceStr to get the same length characters of the target string type P from the original string type and check recursively.

// Get the length of the given string
type StrLen<S extends string, Len extends '🍎'[] = []> =
 S extends `${infer HEAD}${infer TAIL extends string}`
  ? StrLen<TAIL, [...Len, '🍎']>
  : Len['length']

type Test2110401 = StrLen<'aa'>  // 2

// Slice and return the first <Len> characeters of the given string
type SliceStr<S extends string, Len extends number, RES extends string = ''> =
  S extends `${infer HEAD}${infer TAIL extends string}`
    ? StrLen<RES> extends Len
      ? RES
      : SliceStr<TAIL, Len, `${RES}${HEAD}`>
    : RES

type Test2110402 = SliceStr<'abcde', 2> // ab

type FindAll<
  S extends string,
  P extends string,
  COUNT extends '🍎'[] = [],
  RES extends number[] = [],
> = P extends ''
  ? []
  : S extends `${infer HEAD}${infer TAIL extends string}`
  ? SliceStr<S, StrLen<P>> extends P
    ? FindAll<TAIL, P, [...COUNT, '🍎'], [...RES, COUNT['length']]>
    : FindAll<TAIL, P, [...COUNT, '🍎'], RES>
  : RES

Solution by playitsafe #30284

type StringLength<S> = S extends `${infer L}${infer E}` ? [L, ...StringLength<E>] : []
type RemoveFirst<S extends string> = S extends `${string}${infer R}` ? R: S
type FindAll<T extends string, P extends string, R extends any[] = [], Count extends any[] = []> =
  P extends ''
  ? [] : T extends `${infer L}${P}${infer E}`
    ? FindAll<`${RemoveFirst<P>}${E}`, P, [...R, [...Count, ...StringLength<L>]['length']], [...Count, ...StringLength<L>, 1]>
  : R

Solution by sv-98-maxin #30180

// 你的答案
type getStrL<T extends string, U extends ''[] = []> = T extends `${any}${infer R}` ? getStrL<R, [...U, '']> : U['length']
type FindAll<T extends string, P extends string, S extends string = '', R extends number[] = []> =
  P extends '' ? [] :
  T extends `${S}${infer F}${P}${any}` ?
  FindAll<T, P, `${S}${F}${P extends `${infer F}${any}` ? F : P}`, [...R, getStrL<`${S}${F}`>]>
  : R

Solution by YE840926098 #30145

type NormalFindAll<
  T extends string, 
  S extends string,
  P extends any[] = [],
  R extends number[] = [],
> = 
T extends `${string}${infer L}`?
  T extends `${S}${string}`?
    NormalFindAll<L,S,[...P,0],[...R,P['length']]>
    :NormalFindAll<L,S,[...P,0],R>
  :R

type FindAll<
  T extends string, 
  P extends string,
> = 
P extends ''?
  []:NormalFindAll<T,P>

Solution by jiangshanmeta #29712

type FindAll<T extends string, P extends string> = P extends '' ? [] : Helper<T, P>
type Helper<T extends string, P extends string, I extends 1[] = [], R extends number[] = []> =
  T extends ''
    ? R
    : T extends `${P}${string}`
      ? Helper<Tail<T>, P, [1, ...I], [...R, I['length']]>
      : Helper<Tail<T>, P, [1, ...I], R>
type Tail<T extends string> = T extends `${any}${infer Rest}` ? Rest : ''

Solution by Sun79 #29656