检查一个词是否存在于节点的子集中

Question

我正在尝试创建一个函数，它接受一个词、一个板和两个板索引：一个行索引和一个列索引，并且 return 如果该词存在于从行开始的板上，则为真ri, column ci 和 tracing 只从位置 ri, ci 向左或向上移动的路径（就像图表上的 x,y）。

 0 1 2 3 4 5 6 7 8 
0 . . . . . . . . . 
1 . . . . . . . . .
2 . . . . . . . . .
3 . . . . . . . . .
4 . . . . . . . . .
5 . . . . . . . . .
6 . . . . . . . . .

#|
   A Board is one of:
   – empty
   – (cons [ListOf X] Board) -board-cols items long 

   [ListOf X] is board-rows items long

   board? : X -> Bool
   make-board :  Nat Nat X -> Board
|# 
(define-struct board [rows cols content])

这应该在 ISL+ 中，如果需要的话只有一个助手，但没有其他局部变量、助手、lambda、lets 等，并且应该是二叉树递归。

我相信我已经很接近解决这个问题了，但我一直只有一些检查预期通过。这是我所做的：

 ;returns a character at the location
 ;this function doesn't count as a helper
    (define (board-ref b row col)
      (if (or (< (board-rows b) row) (< (board-cols b) col)) false
          (string-ref (list-ref (board-content b) row) col)))    

    ; find? : String Board Row Col -> Bool
        (define (find? w b ri ci)
          (local [(define (help w b ri ci n)
                    (cond 
                      [(= n (sub1 (string-length w))) true]
                      [else 
           (and (equal? (string-ref w n) (board-ref b ri ci))
                (or (equal? (string-ref w n) (help w b (sub1 ri) ci (add1 n)))  
                    (equal? (string-ref w n) (help w b ri (sub1 ci) (add1 n)))))]))] 
        (help w b ri ci 0)))

支票：

(define b0 (make-board 1 1 (list "x")))
(define b1 (make-board 5 5 
                       (list "reuta" "trmfk" "holte" "nsicd" "cexly")))
(define b2 (make-board 3 7 (list "jkialmw" "ienloer" "syilzbt")))
#;(check-expect (find? "x" b0 0 0) true)
#;(check-expect (find? "sort" b1 3 1) true)
#;(check-expect (find? "aikj" b2 0 3) true)
#;(check-expect (find? "aikji" b2 0 3) false)

任何帮助都会大有帮助。

Answer 1

您遇到了三个看起来像这样的问题：

 [(= n (sub1 (string-length w))) true]

如果您尝试运行 (find? "q" b0 0 0) 会发生什么？那显然应该失败，但事实并非如此。您过早地宣布匹配一个字符。（这意味着到处都可以找到单个字符串。）想想单字符的情况； (string-length "q") 为 0。您通过调用 help 并将 n 作为 0 来开始递归。

 (or (equal? (string-ref w n) (board-ref b ri ci))
     (help w b (sub1 ri) ci (add1 n))    
     (help w b ri (sub1 ci) (add1 n)))]))]

考虑一下您将如何向某人解释该代码。它会像 "Return true, if the current character matches, or the recursive call up suceeds, or the recursive call to the left succeeds."

您需要当前字符 ((string-ref w n)) 在每次调用时匹配。 or 与两个递归调用一起发挥作用；你不关心他们中的哪一个成功了，你只需要他们中的一个成功。

  (if (or (< (board-rows b) row)
          (< (board-cols b) col))
      false
      (string-ref (list-ref (board-content b) row) col)))

当您点击顶部或左侧边缘时会发生什么，并且您仍然有您要查找的字母？ row 和 col 会变成负数，然后 list-ref 和 string-ref 不会快乐。在您对 soegaard 的评论中，您说递归应该上升直到达到 0,0。但实际上是什么阻止了你？

检查一个词是否存在于节点的子集中

Check if a word exists in a subset of a node

scheme

racket