题解 | #判断是不是子字符串#Erlang双指针或动态规划

双指针

解题思路

不断遍历匹配T的头部是否含有S的头部，匹配到时将S头部移除直到空列表即为true

代码

-spec is_subsequence(S :: unicode:unicode_binary(), T :: unicode:unicode_binary()) -> boolean().
is_subsequence(S, T) ->
    TList = binary:bin_to_list(T),
    SList = binary:bin_to_list(S),
    do_is_subsequence(TList, SList).

do_is_subsequence([HeadT | T], S = [HeadS | _]) when HeadT =/= HeadS ->
    do_is_subsequence(T, S);
do_is_subsequence([HeadT | T], [HeadS | S]) when HeadT =:= HeadS ->
    do_is_subsequence(T, S);
do_is_subsequence(_, []) ->
    true;
do_is_subsequence(_, _) ->
    false.

动态规划

解题思路

首先用T建立缓存数据，遍历T并建立每个字母的索引列表

然后再遍历S，查询字母索引列表中是否存在合法索引，即索引值大于当前索引的新索引。

代码

-spec is_subsequence(S :: unicode:unicode_binary(), T :: unicode:unicode_binary()) -> boolean().
is_subsequence(S, T) ->
    TList = binary:bin_to_list(T),
    SList = binary:bin_to_list(S),
    do_cache(TList, #{index => 1, list => SList, cache => #{}}).

do_cache([Word | T], Args = #{index := Index, cache := Cache}) ->
    IndexList = maps:get(Word, Cache, []),
    NewIndexList = IndexList ++ [Index],
    do_cache(T, Args#{index := Index + 1, cache := Cache#{Word => NewIndexList}});
do_cache(_, #{list := SList, cache := Cache}) ->
    do_is_subsequence(SList, #{index => 0, cache => Cache}).

do_is_subsequence([Word | S], Args = #{index := PreIndex, cache := Cache}) ->
    IndexList = maps:get(Word, Cache, []),
    %io:format("cache ~w\n", [Cache]),
    %io:format("word ~w pre_index ~w\n", [Word, PreIndex]),
    case [Index || Index <- IndexList, Index > PreIndex] of
        NewIndexList = [NewPreIndex | _] ->
            NewCache = Cache#{Word => NewIndexList},
            do_is_subsequence(S, Args#{index := NewPreIndex, cache := NewCache});
        _ ->
            false
    end;
do_is_subsequence([], _) ->
    true.