Question

How to check whether a string can be segmented into a sequence of words from a dictionary in Pascal

Answer 1

program WordBreakCheck;

const
  DictSize = 8;
  MaxLen = 256;

type
  DictArray = array[1..DictSize] of string;
  BoolArray = array[0..MaxLen] of boolean;

function IsInDict(word: string; dict: DictArray): boolean;
var
  i: integer;
begin
  IsInDict := false;
  for i := 1 to DictSize do
    if dict[i] = word then
    begin
      IsInDict := true;
      exit;
    end;
end;

function WordBreak(s: string; dict: DictArray): boolean;
var
  result: BoolArray;
  i, j, slen: integer;
  subStr: string;
begin
  slen := length(s);
  for i := 0 to slen do
    result[i] := false;
  result[0] := true;

  for i := 1 to slen do
  begin
    for j := 0 to i - 1 do
    begin
      if result[j] then
      begin
        subStr := Copy(s, j + 1, i - j);
        if IsInDict(subStr, dict) then
        begin
          result[i] := true;
          break;
        end;
      end;
    end;
  end;

  WordBreak := result[slen];
end;

var
  dict: DictArray;
  s: string;
begin
  dict[1] := 'future';
  dict[2] := 'depends';
  dict[3] := 'the';
  dict[4] := 'on';
  dict[5] := 'your';
  dict[6] := 'dreams';
  dict[7] := 'start';
  dict[8] := 'today';

  s := 'futuredependsonyourdreams';

  if WordBreak(s, dict) then
    writeln('The string can be segmented')
  else
    writeln('The string cannot be segmented');
end.



(*
run:

The string can be segmented

*)

 

70+ SQL courses for beginners and professionals

Answer 2

program WordBreakSegment;

const
  DictSize = 11;
  MaxLen = 255;

type
  DictArray = array[1..DictSize] of string;

function IsInDict(word: string; dict: DictArray): boolean;
var
  i: integer;
begin
  IsInDict := false;
  for i := 1 to DictSize do
    if dict[i] = word then
    begin
      IsInDict := true;
      exit;
    end;
end;

procedure WordBreak(str: string; strsize: integer; result: string; dict: DictArray);
var
  i: integer;
  subStr: string;
begin
  for i := 1 to strsize do
  begin
    subStr := Copy(str, 1, i);
    if IsInDict(subStr, dict) then
    begin
      if i = strsize then
      begin
        writeln(result + subStr);
        exit;
      end
      else
        WordBreak(Copy(str, i + 1, strsize - i), strsize - i, result + subStr + ' ', dict);
    end;
  end;
end;

var
  dict: DictArray;
  str: string;
begin
  dict[1] := 'butterfly';
  dict[2] := 'basketball';
  dict[3] := 'bagpiper';
  dict[4] := 'and';
  dict[5] := 'play';
  dict[6] := 'with';
  dict[7] := 'butter';
  dict[8] := 'fly';
  dict[9] := 'basket';
  dict[10] := 'ball';
  dict[11] := 'bags';

  str := 'butterflyplaybasketballwithbags';
  WordBreak(str, Length(str), '', dict);
end.



(*
run:

butter fly play basket ball with bags
butter fly play basketball with bags
butterfly play basket ball with bags
butterfly play basketball with bags

*)

 

70+ SQL courses for beginners and professionals