比较字符串的子序列:求解《521. 最长特殊序列 Ⅰ》和《522. 最长特殊序列 II》

2022-06-27 14:35:14
比较字符串的子序列,求解《521. 最长特殊序列 Ⅰ》和《522. 最长特殊序列 II》

例题

521. 最长特殊序列 Ⅰ

给你两个字符串 a 和 b,请返回 这两个字符串中 最长的特殊序列 的长度。如果不存在,则返回 -1 。
「最长特殊序列」 定义如下:该序列为 某字符串独有的最长子序列(即不能是其他字符串的子序列) 。
字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。
例如,"abc" 是 "aebdc" 的子序列,因为删除 "aebdc" 中斜体加粗的字符可以得到 "abc" 。 "aebdc" 的子序列还包括 "aebdc" 、 "aeb" 和 "" (空字符串)。
示例 1:
输入: a = "aba", b = "cdc"
输出: 3
解释: 最长特殊序列可为 "aba" (或 "cdc"),两者均为自身的子序列且不是对方的子序列。

答案

字符串长度 · 最大值

var findLUSlength = function(a, b) {
  return a === b ? -1 : Math.max(a.length, b.length)
};
function findLUSlength(a: string, b: string): number {
  return a === b ? -1 : Math.max(a.length, b.length)
};
func findLUSlength(a string, b string) int {
  if a == b {
    return -1
  }
  return int(math.Max(float64(len(a)), float64(len(b))))
}
class Solution {
  function findLUSlength($a, $b) {
    return $a === $b ? -1 : max(strlen($a), strlen($b));
  }
}
class Solution:
  def findLUSlength(self, a: str, b: str) -> int:
    return -1 if a == b else max(len(a), len(b))
class Solution {
  public int findLUSlength(String a, String b) {
    return a.equals(b) ? -1 : Math.max(a.length(), b.length());
  }
}
public class Solution {
  public int FindLUSlength(string a, string b) {
    return a == b ? -1 : Math.Max(a.Length, b.Length);
  }
}
MAX(a, b) a > b ? a : b
int findLUSlength(char * a, char * b){
  return strcmp(a, b) == 0 ? -1 : MAX(strlen(a), strlen(b));
}
class Solution {
public:
  int findLUSlength(string a, string b) {
    return a == b ? -1 : max(a.size(), b.size());
  }
};

522. 最长特殊序列 II

给定字符串列表 strs ,返回其中 最长的特殊序列 。如果最长特殊序列不存在,返回 -1 。
特殊序列 定义如下:该序列为某字符串 独有的子序列(即不能是其他字符串的子序列)。
s 的 子序列可以通过删去字符串 s 中的某些字符实现。
例如,"abc" 是 "aebdc" 的子序列,因为您可以删除"aebdc"中的下划线字符来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)。
示例 1:
输入: strs = ["aba","cdc","eae"]
输出: 3

答案

枚举 · 双指针 · 字符串长度 · 最大值

var findLUSlength = function(strs) {
  const n = strs.length
  let r = -1
  label: for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i !== j && isSequence(strs[i], strs[j])) {
        continue label;
      }
    }
    r = Math.max(r, strs[i].length)
  }
  return r
};
const isSequence = (s1, s2) => {
  const n1 = s1.length, n2 = s2.length
  if (n1 > n2) return false
  let p1 = p2 = 0
  while (p1 < n1 && p2 < n2) {
    if (s1[p1] === s2[p2]) p1++
    p2++  
  }
  return p1 === n1
}
function findLUSlength(strs: string[]): number {
  const n = strs.length
  let r = -1
  label: for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i !== j && isSequence(strs[i], strs[j])) {
        continue label
      }
    }
    r = Math.max(r, strs[i].length)
  }
  return r
};
function isSequence(s1: string, s2: string) {
  const n1 = s1.length, n2 = s2.length
  if (n1 > n2) return false
  let p1 = 0, p2 = 0
  while (p1 < n1 && p2 < n2) {
    if (s1[p1] === s2[p2]) p1++
    p2++
  }
  return p1 === n1
}
func findLUSlength(strs []string) int {
  r := -1
  for i, s1 := range strs {
    for j, s2 := range strs {
      if i != j && isSequence(s1, s2) {
        goto label
      }
    }
    r = int(math.Max(float64(r), float64(len(s1))))
    label:
  }
  return r
}
func isSequence(s1 string, s2 string) bool {
  n1, n2 := len(s1), len(s2)
  if n1 > n2 {
    return false
  }
  p1, p2 := 0, 0
  for p1 < n1 && p2 < n2 {
    if s1[p1] == s2[p2] {
      p1++
    }
    p2++
  }
  return p1 == n1
}
class Solution {
  function findLUSlength($strs) {
    $n = count($strs);
    $r = -1;
    for ($i = 0; $i < $n; $i++) {
      for ($j = 0; $j < $n; $j++) {
        if ($i !== $j && $this->isSequence($strs[$i], $strs[$j])) {
          continue 2;
        }
      }
      $r = max($r, strlen($strs[$i]));
    }
    return $r;
  }
  function isSequence($s1, $s2) {
    $n1 = strlen($s1);
    $n2 = strlen($s2);
    if ($n1 > $n2) return false;
    $p1 = $p2 = 0;
    while ($p1 < $n1 && $p2 < $n2) {
      if ($s1[$p1] === $s2[$p2]) $p1++;
      $p2++;
    }
    return $p1 === $n1;
  }
}
class Solution:
  def isSequence(self, s1: str, s2: str) -> bool:
    n1, n2 = len(s1), len(s2)
    if n1 > n2: return False
    p1, p2 = 0, 0
    while p1 < n1 and p2 < n2:
      if s1[p1] == s2[p2]: p1 += 1
      p2 += 1
    return p1 == n1
  def findLUSlength(self, strs: List[str]) -> int:
    r = -1
    for i, s1 in enumerate(strs):
      for j, s2 in enumerate(strs):
        if i != j and self.isSequence(s1, s2):
          break
      else:
        r = max(r, len(s1))
    return r
class Solution {
  public int findLUSlength(String[] strs) {
    int n = strs.length, r = -1;
    label: for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i != j && isSequence(strs[i], strs[j])) continue label;
      }
      r = Math.max(r, strs[i].length());
    }
    return r;
  }
  public boolean isSequence(String s1, String s2) {
    int n1 = s1.length(), n2 = s2.length();
    if (n1 > n2) return false;
    int p1 = 0, p2 = 0;
    while (p1 < n1 && p2 < n2) {
      if (s1.charAt(p1) == s2.charAt(p2)) p1++;
      p2++;
    }
    return p1 == n1;
  }
}
public class Solution {
  public int FindLUSlength(string[] strs) {
    int n = strs.Length, r = -1;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i != j && isSequence(strs[i], strs[j])) {
          goto label;
        }
      }
      r = Math.Max(r, strs[i].Length);
      label:;
    }
    return r;
  }
  public bool isSequence(string s1, string s2) {
    int n1 = s1.Length, n2 = s2.Length;
    if (n1 > n2) return false;
    int p1 = 0, p2 = 0;
    while (p1 < n1 && p2 < n2) {
      if (s1[p1] == s2[p2]) p1++;
      p2++;
    }
    return p1 == n1;
  }
}
MAX(a, b) a > b ? a : b
bool isSequence(char* s1, char* s2) {
  int n1 = strlen(s1), n2 = strlen(s2);
  if (n1 > n2) return false;
  int p1 = 0, p2 = 0;
  while (p1 < n1 && p2 < n2) {
    if (s1[p1] == s2[p2]) p1++;
    p2++;
  }
  return p1 == n1;
}
int findLUSlength(char ** strs, int strsSize){
  int r = -1;
  for (int i = 0; i < strsSize; i++) {
    for (int j = 0; j < strsSize; j++) {
      if (i != j && isSequence(strs[i], strs[j])) goto label;
    }
    r = MAX(r, (int)strlen(strs[i]));
    label:;
  }
  return r;
}
class Solution {
public:
  bool isSequence(string s1, string s2) {
    int n1 = s1.size(), n2 = s2.size();
    if (n1 > n2) return false;
    int p1 = 0, p2 = 0;
    while (p1 < n1 && p2 < n2) {
      if (s1[p1] == s2[p2]) p1++;
      p2++;
    }
    return p1 == n1;
  }
  int findLUSlength(vector<string>& strs) {
    int n = strs.size(), r = -1;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i != j && isSequence(strs[i], strs[j])) {
          goto label;
        }
      }
      r = max(r, (int)strs[i].size());
      label:;
    }
    return r;
  }
};

代码
自增 ID、RabinKarp 哈希算法和随机数:求解《535. TinyURL 的加密与解密》
自增 ID、RabinKarp 哈希算法和随机数,求解《535. TinyURL 的加密与解密》
代码
字符串的 Unicode 码与字符转换,求解《709. 转换成小写字母》《1309. 解码字母到整数映射》和《953. 验证外星语词典》
字符串的 Unicode 码与字符本身的转换,求解《709. 转换成小写字母》《1309. 解码字母到整数映射》和《953. 验证外星语词典》
代码
哈希映射 + 滑动窗口:求解《438. 找到字符串中所有字母异位词》和《30. 串联所有单词的子串》
哈希映射 + 滑动窗口,求解《438. 找到字符串中所有字母异位词》和《30. 串联所有单词的子串》