cft
Become a CreatorSign inGet Started

LeetCode 567. Permutation in String in F#

LeetCode Daily Program at 2022/02/11


user

Shohei Yoshida

5 months ago | 2 min read
Follow

URL

https://leetcode.com/problems/permutation-in-string/

Code

https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/problems/0567/main.fsx

let splitString (s: string) (len: int) : char list list =

let rec splitString' cs len acc =

if (List.length cs) < len then

acc |> List.rev

else

let v = cs |> List.take len

splitString' (List.tail cs) len (v :: acc)

let cs = s |> Seq.toList

splitString' cs len []

let strToIndexes (s: string) : int list =

s

|> Seq.toList

|> List.map (fun c -> (int c) - (int 'a'))

let charListToIndexes (cs: char list) : int list =

cs |> List.map (fun c -> (int c) - (int 'a'))

let toFreqTable (indexes: int list) : (int []) =

let rec toFreqTable' indexes (acc: int []) =

match indexes with

| [] -> acc

| head :: tail ->

acc.[head] <- acc.[head] + 1

toFreqTable' tail acc

toFreqTable' indexes (Array.init 26 (fun _ -> 0))

let equalFreqTable (a: int []) (b: int []) (len: int) : bool =

let rec equalFreqTable' (a: int []) (b: int []) i len =

if i > len then true

else if a.[i] <> b.[i] then false

else equalFreqTable' a b (i + 1) len

equalFreqTable' a b 0 len

let checkInclusion (s1: string) (s2: string) : bool =

let s1Len = Seq.length s1

let s1Table = strToIndexes s1 |> toFreqTable

let s2Tables =

splitString s2 s1Len

|> List.map (charListToIndexes >> toFreqTable)

s2Tables

|> List.tryFind (fun t -> equalFreqTable s1Table t s1Len)

|> Option.isSome

Upvote


user
Created by

Shohei Yoshida

Follow

A programmer of DeNA

A Programmer


people
Post

Upvote

Downvote

Comment

Bookmark

Share


Related Articles