35045-medium-longest-common-prefix

Back

type LongestCommonPrefix<
  T extends string[],
  P extends string = ""
> = T[number] extends `${P}${infer F}${infer _}`
  ? Equal<[F], F extends any ? [F] : never> extends true
    ? LongestCommonPrefix<T, `${P}${F}`>
    : P
  : P;

思路如下:

  1. 通过联合类型分布式提取所有项某一位置的字符

  2. 提取的结果F如果是联合类型,说明不是所有项该位置字符都相同,返回当前P;反之则都相同,存入P进行下一轮判断

Solution by Barrenboat #37354

type UnionToIntersection<T> = (T extends T ? (args: T) => any : never) extends (args: infer P) => any ? P : never;
type UnionLast<T> = (UnionToIntersection<T extends T ? () => T : never>) extends () => infer R ? R : never;
type UnionToTuple<T> = [T] extends [never] ? [] : [UnionLast<T>, ...UnionToTuple<Exclude<T, UnionLast<T>>>];
type IsUnion<T, U = T> = U extends T ? [Exclude<T, U>] extends [never] ? false : true : never;

type LongestCommonPrefix<T extends string[], P extends string = ''> = T[number] extends `${infer F}${infer R}` ?
  IsUnion<F> extends false ? UnionToTuple<R> extends infer UR extends string[] ? LongestCommonPrefix<UR, `${P}${F}`> :
  P : P : P;

Solution by E-uler #35365

type IsSingle<V, U = V> = V extends unknown ? [U] extends [V] ? true : false : never;

// Longest Common Prefix for string literals union
type LCP<S, R extends string = ''> = [S] extends [`${infer F}${infer T}`]
    ? true extends IsSingle<F>
        ? LCP<T, `${R}${F}`>
        : R
    : R;

type LongestCommonPrefix<T extends string[]> = LCP<T[number]>;

Solution by alexandroppolus #35292

type LongestCommonPrefix<T extends string[], P extends string = ''>
  = T extends [`${P}${infer Next}${any}`, ...any]
  ? T extends `${P}${Next}${any}`[]
    ? LongestCommonPrefix<T, `${P}${Next}`>
    : P // the longest
  : P   // T is empty or end of T[0]

Playground

type LongestCommonPrefix<T extends string[], P extends string = ''>
  = T extends `${P}${infer Next}${any}`[]
  ? {} extends {[P in Next as Exclude<Next, P>]: 1}
    ? LongestCommonPrefix<T, `${P}${Next}`>
    : P // Next is union, return P
  : P   // T is empty or all empty string

Playground

Solution by teamchong #35251